Bit Manipulation

Bit Manipulation

Bit manipulation is the process of applying logical operations on a sequence of bits to achieve a required result. Like in decimal format, we do addition, subtraction, multiplication and division. Similarly, we can apply some operation to manipulate bits of numbers.

In Binary notation, we use 1’s and 0’s to represent numbers.

For ex : 5 => 101
14 => 1110

One way of saying that some bit at some position is 1 or 0, we say bit is set or on when it is 1 and not set or off when it is 0.

Those operators are known as bitwise operators.
There are six types of bitwise operators.

& ( AND )
| ( OR )
^ ( XOR )
<< ( LEFT SHIFT )
>> ( RIGHT SHIFT )
~ ( NOT )

We will be covering the first five of these in this blog, these are the ones that are mostly used.

AND &

Bitwise AND &

bit a   |  bit b  | a & b (a AND b)
0           0          0
0           1          0
1           0          0
1           1          1

We can use & operation to calculate the number of set bits in some number.

To understand that, we first need to go through an observation.

Let’s take a number.
For ex : 42 (110100), if we subtract 1 from 42 it will become 41 that is 110011

One thing that we can notice in this is that all the bits that are after the first set bit (from right) in 42 turned to 1 and that itself turned to 0.

Similarly, in all numbers once we decrement it by 1 all the bits that are after the first set bit (from left) will turn into 1 and that itself will turn into 0.

For ex : 10 => 1010 9 => 1001
14 => 1110 13 => 1101

To calculate number of bits in log(n) time :

int count = 0;
while(n>0){
    count++;
    n = n&(n-1);
}

In the above written code, every time n is going inside the loop it is losing one set bit and incrementing the count by 1. And that will be the total numbers of set bit in n.

BITWISE OR ( | )

bit a |  bit b |  a | b (a OR b)
0       0         0
0       1         1
1       0         1
1       1         1

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.

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.

Some properties of xor :

A ^ A = 0
A ^ 0 = A
A ^ ( B ^ C) = ( A ^ B ) ^ C
A ^ B = B ^ A

One of the important things is that, if we are taking xor of many numbers. We can say that the result will have 1 at some position if the count of numbers with 1 at that position is odd, otherwise it will be zero.

Using the above observation. We can say that, if we calculate xor of first n natural numbers, then it will depend upon remainder that we get on n%4.

If it is 0.
Then answer = n.
If it is 1.
Then answer = 1.
If it is 2.
Then answer = n + 1.
If it is 3.
Then answer = 0.

Left Shift (<<)

If we apply left shift to a number with x units ( 5<<x) this means that we are shifting bits of number to the left by x units and all the empty positions on the right will be filled with 0.

Mathematically, on applying left shift to a number by x units it gets multiplied by 2^x.

For ex : 3<<1 = 2X3 = 6 ( 110 ) [ 3( 11 )]
3<<2 = 4X3 = 12 ( 1100)

9<<3 = 8X9 = 72 (1001000) [9( 1001 )]

Right Shift (>>)

This is just opposite of the left shift, on applying it to a number with x units it shifts bits to right by x units.

Mathematically, on applying the right shift to a number by x units it gets divided by 2^x.

For ex : 3>>1 = 3/2 = 1
3>>2 = ¾ = 0

Some nice way to use these bitwise operations :

First of all, we can use these to solve real life problems, but obviously it will depend upon how we can apply bitmask.

Short tricks that we can use daily in our code are as follows :
To calculate some power of 2, we can directly write it as 1<<x which will be equal to 2^x.
We can use & and << together to check whether a bit at some position is on or off.

bool on(int n, int position){
    int PowerOf2 = 1<<position;
    return ((n&PowerOf2)==0)? false : true;
}

Suggestions are welcomed, to make this blog better.