Bit Algorithm - Learnengineeringforu

Bit Algorithms

Bit manipulation is the process of manipulating bits which are used to represent some word in memory .bit manipulation requires low level programming as we are completely working on the bits i.e 0,1. Application of the bit manipulation is in finding of errors and correcting them , compressing and encrypting data . All new generation programming languages will allow programmer to deal with abstractions which are user understandable rather than using bits which is machine understandable . Source code of the program which uses bit manipulation will use different bitwise operations: bitwise AND, bitwise OR, bitwise XOR, bitwise NOT, and bitwise bit shifts.

Bitwise operations

Any bitwise operation will operates either on one or more bits . It is the fastest and older approach used by the CPU .Such operations will manipulate the values for comparisons and calculations. Bitwise operations are machine understandable and hence faster. Bitwise operations will use less power because of least use of the resources.

Bitwise Operators

Bitwise operator used to work on bits there by performing bit-by-bit operation.

Operator	Description	Example
&	Bitwise AND Operator will result 1 if both the bits are 1.	A & B
|	Bitwise OR Operator will result in 1 if either both the bits are 1 of any of the one bit is 1 .	A | B
^	Bitwise XOR Operator results in 1 if one of the bits is 1 but not both.	A ^ B
~	Bitwise Complement will 'flip' bits resulting 0 in 1 and 1 in 0.	~A
<<	Bitwise Left Shift Operator will shift the bits specified to left	A << 2
>>	Bitwise Right Shift Operator will shift the bits specified to right.	A >> 2

Bitwise operator AND ( &)

bit A	bit B	A & B
0	0	0
0	1	0
1	0	0
1	1	1

Bitwise AND operation of two integers 13 and 24.

13 = 00001101 (In Binary)
24 = 00011000 (In Binary)

Bitwise operator OR ( | )

Operator	Description	Example
&	Bitwise AND Operator will result 1 if both the bits are 1.	A & B
|	Bitwise OR Operator will result in 1 if either both the bits are 1 of any of the one bit is 1 .	A | B
^	Bitwise XOR Operator results in 1 if one of the bits is 1 but not both.	A ^ B
~	Bitwise Complement will 'flip' bits resulting 0 in 1 and 1 in 0.	~A
<<	Bitwise Left Shift Operator will shift the bits specified to left	A << 2
>>	Bitwise Right Shift Operator will shift the bits specified to right.	A >> 2

Bitwise operator AND ( &)

bit A	bit B	A| B
0	0	0
0	1	1
1	0	1
1	1	1

13 = 00001101 (In Binary)
24 = 00011000 (In Binary)

Bitwise OR Operation of 13 and 24

Bitwise operator XOR ( ^)

Operator	Description	Example
&	Bitwise AND Operator will result 1 if both the bits are 1.	A & B
|	Bitwise OR Operator will result in 1 if either both the bits are 1 of any of the one bit is 1 .	A | B
^	Bitwise XOR Operator results in 1 if one of the bits is 1 but not both.	A ^ B
~	Bitwise Complement will 'flip' bits resulting 0 in 1 and 1 in 0.	~A
<<	Bitwise Left Shift Operator will shift the bits specified to left	A << 2
>>	Bitwise Right Shift Operator will shift the bits specified to right.	A >> 2

Bitwise operator AND ( &)

bit A	bit B	A ^ B
0	0	0
0	1	1
1	0	1
1	1	0

13 = 00001101 (In Binary)
24 = 00011000 (In Binary)

Bitwise XOR Operation of 13 and 24

Bitwise complement "~"

bit A	~A
0	1
1	0

13 = 00001101 (In Binary)

Bitwise complement of 13

Complement of 00001101 is 11110010

Shift Operators

There are two bit shifting operators :

• Right shift
• Left shift

Right Shift Operator

13 = 00001101 (In Binary)

13>>3 = 00000001 (In binary) [Right shifting bits by three bits]

Left Shift Operator

13 = 00001101 (In Binary)

13<<2 = 00110100(In binary) [left shifting bits left by two bit]

13<<0 =00001101  (Shift by 0)

Example:-

#include
int main()
{
unsigned char p = 5, q = 9; // p = 4(00000101), q = 8(00001001)
printf("p = %d, q = %d\n", p, q);
printf("p&q= %d\n", p&q); 
printf("p|q = %d\n", p|q);  
printf("p^q = %d\n", p^q); 
printf("~p = %d\n", p = ~p);   
printf("q<<1 = %d\n", q<<1);  
printf("q>>1 = %d\n", q>>1);  
return 0;
}

Output:

p = 5, q = 9

p&q = 1

p|q = 13

p^q = 12

~p = 250

q<<1 = 18

q>>1 = 4

Sample Tutorial Problem

Any positive integer can be represented by a four digit binary number. For example 0 is represented by binary 0000, 1 is represented by 0001, 2 is represented by 0010 and so on. In this binary representation a bit is called set if it is 1. You need to write a program to input an integer and find next greater integer who has one more number of set bits in its binary representation.

Input Format

It will be an integer number n.

Constraints

0 <= n <= 100

Output Format

It will an integer number greater than n having one more set bits in binary representation than n.

Sample TestCase 1

Input

10

Output

11                                                                  C ( gcc 4.9.2 )                                                                   C++ ( g++ 4.9.2 )                                                                   C# ( mono 3.2.8 )                                                                   Java ( java 1.7.0_80 )                                                                   Java 8 ( 1.8.0_45 )                                                                   PHP ( php 5.6.8-1 )                                                                   Python ( python 2.7.6 )                                                                   Python 3 ( Python 3.4.0 )                                                                   Perl ( perl 5.18.2 )                                                                   Ruby ( ruby 2.1.6p336 )                                                                   Node Js ( v5.4.1 )                                                                   Scala ( scala 2.11.3 )                                                                   Clojure ( clojure 1.7.0 )                                                                   Haskell ( ghc 7.10.1 )                                                                   Lua ( Lua 5.2.3 )                                                                   Erlang ( Erlang/OTP 18 )                                                                   VBnet ( mono 3.2.8 )                                                                   Js ( Rhino 1.7 )                                                                   Objc ( clang 3.4 )                                                                   Pascal ( fpc 2.6.2-8 )                                                                   Go ( go 1.4.2 )                                                                   F# ( Fsharp 3.0.34 )                                                                   D ( Version 2.067.1 )                                                                   Groovy ( Groovy 1.8.6 )                                                                   Tcl ( Version 8.6.0+6 )                                                                   Ocaml ( ocamlopt 4.01.0 )                                                                   Smalltalk ( smalltalk 3.2.43.2.4 )                                                                   Cobol ( (OpenCOBOL) 1.1.0 )                                                                   Racket ( Version 6.2 )                                                                   Bash ( Version 4.3.11 )                                                                   GNU Octave ( GNU Octave 4.0.0 )                                                                   Rust ( Rustc 1.5.0 )                                                                   Common LISP ( GNU CLISP 2.49 )                                                                   R ( R 3.0.2 )                                                              

Compile & Run

1

2

3

4

5

6

7



















/* Read input from STDIN. Print your output to STDOUT*/



#include<stdio.h>



int main(int argc, char *a[])



{



    //Write code here



}

Submit Code

Compile & Run