Prerequisites

Every thing you need to know before starting Bit Manipulation.

Bitwise Operators:

There are different bitwise operations used in the bit manipulation. These bit operations operate on the individual bits of the bit patterns. Bit operations are fast and can be used in optimizing time complexity. Some common bit operators are:

NOT ( ~ ):

Bitwise NOT is an unary operator that flips the bits of the number i.e., if the ith bit is 0, it will change it to 1 and vice versa. Bitwise NOT is nothing but simply the one’s complement of a number. Lets take an example.

1
N = 5 = (101)
2
~N = ~5 = ~(101) = (010) = 2

AND ( & ):

Bitwise AND is a binary operator that operates on two equal-length bit patterns. If both bits in the compared position of the bit patterns are 1, the bit in the resulting bit pattern is 1, otherwise 0.

1
A = 5 = (101)
2
B = 3 = (011)
3
A & B = (101) & (011) = (001) = 1

OR ( | ):

Bitwise OR is also a binary operator that operates on two equal-length bit patterns, similar to bitwise AND. If both bits in the compared position of the bit patterns are 0, the bit in the resulting bit pattern is 0, otherwise 1.

1
A = 5 = (101)
2
B = 3 = (011)2
3
A | B = (101)2 | (011)2 = (111)2 = 7

XOR ( ^ ):

Bitwise XOR also takes two equal-length bit patterns. If both bits in the compared position of the bit patterns are 0 or 1, the bit in the resulting bit pattern is 0, otherwise 1.

1
A = 5 = (101)
2
B = 3 = (011)
3
A ^ B = (101) ^ (011) = (110) = 6

Left Shift (`<<`):

Left shift operator is a binary operator which shift the some number of bits, in the given bit pattern, to the left and append 0 at the end. Left shift is equivalent to multiplying the bit pattern with 2k ( if we are shifting k bits ).

1
1 << 1 = 2 = 21
2
1 << 2 = 4 = 22 1 << 3 = 8 = 23
3
1 << 4 = 16 = 24
4
…
5
1 << n = 2n

Right Shift (`>>`):

Right shift operator is a binary operator which shift the some number of bits, in the given bit pattern, to the right and append 1 at the end. Right shift is equivalent to dividing the bit pattern with 2k ( if we are shifting k bits ).

1
4 >> 1 = 2
2
6 >> 1 = 3
3
5 >> 1 = 2
4
16 >> 4 = 1