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