September 19, 2021

Howdy fellow devs ๐! Since we are in the field of making computer do our tasks, we know that computers donโt understand words and letters like we do. They only understand **binary** โ a sequence of zeroes and ones. This series of 0s and 1s are called **bits**.

There are many problems which can be solved by manipulating bits. In this post (and hopefully, in subsequent parts), we will look at some common problems which can be easily solved using bit manipulation. In my opinion, the solutions are not intuitive and can be a bit difficult to write or maintain but as a self-respecting software engineer, we should know these techniques ๐ช.

So, without further ado, letโs see some problems.

**Given an integer an n, return the position of first set bit found from the right side in the binary representation of the number.
For example - binary representation of 22 is 10110, and the position of first set bit is 2.
**

For non-zero inputs, we can find the position of first set bit by **ANDing** the `n`

with a variable `mask`

which has initial value of 1 and will **left shift (<<)** after each iteration. The **AND** will yield zero as long as we are encountering zero (from right) in `n`

. The moment we get 1 as the output of **AND**, we will return the count of iterations we have made till that point as answer.

The code for the idea is below โ

```
public class FindFirstSetBit {
public int getFirstSetBit(int n) {
// Special case
if (n == 0) {
return 0;
}
// Position of the first set bit from the right
int position = 1;
// Variable for shifting
int mask = 1;
// Counting the position of first set bit
while ((n & mask) == 0) {
position++;
mask <<= 1;
}
return position;
}
}
```

**Given two numbers m and n, find the position of the rightmost different bit in the binary representation of numbers.
**

This is the extension of the previous problem. We know that if we take **XOR** of two numbers, then 1 will be present in the output at places which have different bits in the given numbers. Therefore, if we find the position of first set bit in the **XOR**, then we will have our answer.

The code for this idea is below -

```
public class RightMostDifferentBit {
public int posOfRightMostDiffBit(int m, int n) {
// Find the XOR of both numbers to get 1 at the position
// of difference in bits
int xor = m ^ n;
// Special case
if (xor == 0) {
return 0;
}
// Now find the position of the rightmost set bit
// Position of the first set bit from the right
int position = 1;
// Variable for shifting
int mask = 1;
// Counting the position of first set bit
while ((xor & mask) == 0) {
position++;
mask <<= 1;
}
return position;
}
}
```

**Given a number n and an integer k, check if k ^{th} bit of n is set or not.**

This is a bit tricky problem and not intuitive (in my opinion ๐). The first thing we can do is shift our `mask`

by `k`

positions and then negate it. For example, if `k = 3`

, our `mask`

will become `1000`

after shifting `k`

times, then we will negate it, so it will become `0001`

. Now, if we take **OR** the resultant value with `n`

, we will get a string of all `1s`

, if the k^{th} bit is 1, otherwise not.

The code is below โ

```
public class CheckKthBit {
public boolean checkKthBit(int n, int k) {
// Variable for shifting
int mask = 1;
// Shift k positions
for (int i = 0; i < k; i++) {
mask <<= 1;
}
// Negate the shift
mask = ~mask;
// OR the shift with n
return (mask | n) == ~0;
}
}
```

**Given a number n and a value k. From the right, set the k ^{th} bit in the binary representation of n.**

This is pretty simple, we will take a `mask`

with initial value 1, and then shift it to `k`

positions which will result in k^{th} bit of mask to 1 and remaining bits 0. Then we will perform **OR** with `n`

to get our final answer.

The code for this idea is below โ

```
public class SetKthBit {
public int setKthBit(int n, int k) {
return n | (1 << (k));
}
}
```

**Given a non-negative integer n, check if n is a power of 2.**

The powers of two are 2,4,8,16,32,โฆ and so on. Note that in the binary representation of any number which is a power of 2, we have only MSB set, and all remaining bits are 0. Now, for all numbers which are 1 less than a number which is power of 2, all bits are 1. See few examples below โ

```
2 -> 10 1 -> 1
4 -> 100 3 -> 11
8 -> 1000 7 -> 111
16 -> 10000 15 -> 1111
```

Itโs now intuitive that if we **AND** `n`

and `n-1`

, then we will get 0 for all powers of two. Following code shows this idea -

```
public class PowerOfTwo {
public boolean isPowerOfTwo(long n){
if (n <= 0) {
return false;
}
return (n & (n - 1)) == 0;
}
}
```

**Given two numbers A and B, count the number of bits needed to be flipped to convert A to B.**

Our first task is to find different bits (at the same place) in `A`

and `B`

. The logical operation that comes to our mind for such task is **XOR**. After **XORing** `A`

and `B`

, we will get 1 at places where bits were different. Now, our task comes down to find out the count of 1s in the **XOR** output.

The code for this idea is below โ

```
public class BitDifference {
public int countBitsFlip(int a, int b) {
// Find XOR of two numbers to find out different bits
int xor = a ^ b;
// Count of 1s in the XOR output
int count = 0;
// Loop until xor becomes 0
while (xor != 0) {
xor &= (xor - 1);
count++;
}
return count;
}
}
```

**Given a number n, check whether it is sparse or not. A number is said to be a sparse number if no two or more consecutive bits are set in the binary representation.**

If we left shift `n`

by 1 and **AND** it with itself, we should be able to determine if the number is parse or not. Letโs understand this with example, suppose `n = 1100111`

, then `n << 1 => 1001110`

.
Now, `n & (n << 1) => 1100111 & 1001110 => 1000110 != 0`

, hence this number is not sparse.
Letโs take another example, `n = 100101`

, then `n << 1 => 001010`

. Now, `n & (n << 1) => 000000 == 0`

, hence this number is a sparse number.

```
public class SparseNumber {
public boolean isSparse(int n) {
return (n & (n << 1)) == 0;
}
}
```

**Given a non-empty array of integers nums, every element appears twice except for one. Find that single one.**

Itโs simple ๐. If we take **XOR** of a number with itself, we get 0, so if we **XOR** all numbers in the array, the pairs will cancel out each other, and we will be left with the number which is appearing once in the array.

```
public class SingleNumber {
public int findSingle(int[] nums) {
int xor = nums[0];
for (int i = 1; i < nums.length; i++) {
xor ^= nums[i];
}
return xor;
}
}
```

**Given a non-negative number N and two values L and R, toggle the bits in the range L to R in the binary representation of N, i.e, to toggle bits from the rightmost Lth bit to the rightmost Rth bit.**

The problem is asking for toggling the bits (forget about the range now!). Which logical operation can help us in toggling ๐ค? Yes, the **XOR** operation!!! Letโs see how, if we XOR 1 with 1, we will get 0, and if we XOR 0 with 1, we get 1. See, toggle happens ๐.

Thus, we can solve this problem by **XORing** the number `N`

with a `mask`

having `R`

bits and only set bits are present in the range `L`

to `R`

. We can get such `mask`

by using the following expression `mask = ((1 << R) - 1) ^ ((1 << (L - 1)) - 1)`

.

```
public class ToggleBitsInRange {
public int toggleBits(int N, int L, int R) {
int mask = ((1 << R) - 1) ^ ((1 << (L - 1)) - 1);
return N ^ mask;
}
}
```

**Given an integer N and an integer D, rotate the binary representation of the integer N by D digits to the left as well as right and print the results in decimal values after each of the rotation. Note: Integer N is stored using 16 bits. i.e. 12 will be stored as 0000.....001100.**

In `N << D`

, last `D`

bits are zero, to put first `D`

bits at the end for rotation, we will **OR** with `N >> (16 - D).`

Vice versa is true for right shift.

```
public class RotateBits {
public List<Integer> rotate(int N, int D) {
// Reduce D to its effective value for a 16 bit number
D %= 16;
// This list will store the left and right rotations of N by D
List<Integer> output = new ArrayList<>();
// Left rotation
int left = (N << D | N >> (16 - D)) & 0xFFFF;
// Right rotation
int right = ((N >> D | N << (16 - D))) & 0xFFFF;
output.add(left);
output.add(right);
return output;
}
}
```

In this post, we looked at some common problems that can be solved using simple tricks with the bits.

I hope you enjoyed this post. Feel free to share your thoughts on this.

You can find the complete source code on my GitHub repository. If you like what you learned, feel free to fork ๐ช and star โญ it.

Till next timeโฆ Happy coding ๐ and Namaste ๐!