Bit Manipulation Tricks for interviews

Right shift operator is equivalent to division by 2.

You can divide a number by 2 by using the >> operator.

Example :

 16 = 00010000 in binary format
 
 00010000 >> 1 = 00001000
 
 00001000 = 8 in decimal format = 16 / 2

PS : x >> y is equivalent to dividing x with 2^y

Left shift operator is equivalent to multiplication by 2.

You can multiply a number by 2 by using the << operator.

Example :

 16 = 00010000 in binary format
 
 00010000 << 1 = 00100000
 
 00100000 = 32 in decimal format = 16 x 2

PS: x << y is equivalent to multiplying x with 2^y

Use bitwise AND operator to check even or odd number

You can check if a number is Odd or even by using the Modulo Operator. Check out the pseudo code below

if(num % 2 == 0){
   //num is Odd
} else {
 //num is Event
}

An alternate way to check this is by doing a Bitwise & with 1

if(num & 1 == 0) {
   // Number is even
} else {
   // Number is odd
}

This is because the Least Significant Bit for odd numbers is always set. Hence doing an & will always return 1. For even numbers it will always return 0.

Check whether n is a power of 2 or not

If the number is n, then using the formulae n & (n-1) == 0 - you can know if a number is power of two or not.

Here is the explanation for how it works :

Any power of 2 minus 1 is all ones: ( = 111....1 in binary notation)

2 = 2^1.  2-1 = 1 (1 in binary notation)
4 = 2^2.  4-1 = 3 (11 in binary notation)
8 = 2^3.  8-1 = 7 (111 in. binary notation)

Hence doing n & (n-1) will always return 0.

Here are a few examples of the same :

n = 8 (1000 in binary notation)
n - 1 = 7 (0111 in binary notation)
n & (n-1) =  1000 & 0111 = 0000. 
Hence 8 it is a power of 2

n = 16 (10000 in binary notation)
n - 1 = 15 (01111 in binary notation)
n & (n-1) =  10000 & 01111 = 0000. 
Hence 16 it is a power of 2.

n = 17 (10001 in binary notation)
n - 1 = 16 (10000 in binary notation)
n & (n-1) =  10001 & 10000 != 0000. 
Hence 17 it is not a power of 2

Create a number that has only the Kth bit set

Number 1 has its 1st bit set. So take one and left shift (<<) it by k - 1 to set the bit.

//Number with 4th bit set
00000001 << (4 - 1) = 00000001 << 3 = 0001000

//Number with 7th bit set
00000001 << (7 - 1) = 00000001 << 6 = 01000000

Check whether the Kth bit is set or not

We just learnt above to set the bit using the formulae 1 << (k - 1). So to check if this bit is set or not, we can do a Bitwise and to see if that bit is set or not.

Hence using the equation n & (1 << (k - 1)) != 0 one can determine if the is set or not.

//n = 1101010, k = 4
1101010 & (1 << (4 - 1)) = 1101010 & 0001000 = 0001000 => This is not equal to zero and hence the 4th bit is set for this number

//n = 1100010, k = 4
1100010 & (1 << (4 - 1)) = 1100010 & 0001000 = 0000000 => This is equal to zero and hence the 4th bit is not set for this number

Set the Kth bit to 1

As we saw above that 1 << (k - 1) will result in a number whose only bit is set.

Now doing a bitwise OR with the original number will ensure that that bit is set.

//n = 1101010, k = 4
1101010 | (1 << (4 - 1)) = 1101010 | 0001000 = 1101010 => Here the bit was already set. 

//n = 1100010, k = 4
1100010 | (1 << (4 - 1)) = 1100010 | 0001000 = 1101010 => Check the 4th bit, it is set now

Clearing the Kth bit

Step 1 : As we saw above that 1 << (k - 1) will result in a number whose only bit is set.

Step 2 : Doing a bitwise NOT on this ~(1 << (k - 1)) will result in a number where all the bits are set except the bit

Step 3 : Now doing a bitwise AND on this will keep the other bits as same and only clear the bit.

//n = 1101010, k = 4
Step 1 : (1 << (k - 1)) = (1 << (4 - 1)) = 00001000
Step 2 : ~(1 << (k - 1)) = ~(1 << (4 - 1)) = ~(00001000) = 11110111
Step 3 : n & ~(1 << (k - 1)) = 1101010 & 11110111 = 1100010

Toggling the Kth bit

Step 1 : As we saw above that 1 << (k - 1) will result in a number whose only bit is set.

Step 2: Now doing a bitwise XOR on this will keep the other bits as same and only toggle the bit.

//n = 1101010, k = 4
Step 1 : (1 << (k - 1)) = (1 << (4 - 1)) = 00001000
Step 2 : n ^ (1 << (k - 1)) = 1101010 ^ 00001000 = 1100010

Find the total number of bits in a binary representation of a number

Explanation :

for example :

(binary representation of 16 is 10000) => Number of bits = 4 + 1 = 5

(binary representation of 17 is 10001) => Number of bits = 4 + 1 = 5

Alternatively you can use base 10 log function

Explanation :

for example :

(binary representation of 16 is 10000) => Number of bits = 4 + 1 = 5

Number of set bits in a binary representation of a number

Brian Kernighan’s Algorithm : It states that if we perform AND operation of the number with number-1, we actually unset it’s rightmost bit. So keep on doing this until the number becomes zero.

Iterate number = number & (number-1), till number != 0 and increment the counter at each step.

Swap two numbers without using any temporary variable

Use bitwise XOR (^) operator to quickly swap two number without third variable

 // Swap a with b
 a ^= b;
 b ^= a;
 a ^= b;

Finding 1's complements of a number

One's complement of a number is obtained by toggling all bits of a number.

1's complement of "0111" is "1000"
1's complement of "1100" is  "0011" 

You can achieve this by using the unary operator (~)

one's complement = ~(number)

Finding 2's complements of a number

Twos complement of a number is one's complement + 1.

two's complement = ~(number) + 1

Store multiple flags in a single variable

Example when you can use a single variable to keep multiple boolean flags like, isMarried, isStudent, isWorking. Reduces the amount of space you use to store the information.

Find maximum or minimum without if else

min = (y ^ (x ^ y) & -(x < y));

max = (x ^ (x ^ y) & -(x < y))