# 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))`