# Bit Hacks – Part 3 (Playing with rightmost set bit of a number)

In this post we will discuss few related problems that are related to unsetting the rightmost set bit of a number.

###### How to unset the rightmost set bit of a number?

The expression (n & (n – 1)) will turn off the rightmost set bit of given number. (n – 1) will have all the bits flipped after the rightmost set bit of n (including the rightmost set bit).
So (n & (n – 1)) will result in last bit flipped of n. Consider

00010100   &                 (n = 20)
00010011                     (n-1 = 19)
~~~~~~~~
00010000

00…00000000   &              (n = 0, no rightmost bit)
11…11111111                  (n-1 = -1)
~~~~~~~~~~~
00…00000000

Below problems can be solved by unset the rightmost set bit of a number –

Problem 1. Check if given positive integer is a power of 2 without using any branching or loop.

As discussed above, the expression (n & (n – 1)) will unset the rightmost set bit of a number. If the number is power of 2, it has only one bit set and (n & (n – 1)) will unset the only set bit. So we can say that (n & (n – 1)) returns 0 if n is power of 2 else it is not a power of 2.

For example,

00010000   &             (n = 16, only one set bit)
00001111                 (n-1 = 15)
~~~~~~~~
00000000

Problem 2. Find position of the rightmost set bit

The idea is to unset the rightmost bit of number n and XOR the result with n. Then the position of the rightmost set bit in n will be the position of the only set bit in the result. Note that if n is odd, we can directly return 1 as first bit is always set for odd numbers.

For example, number 20 in binary is 00010100 and position of the rightmost set bit is 3.

00010100   &                   (n = 20)
00010011                       (n-1 = 19)
~~~~~~~~
00010000   ^                   (XOR result number with n)
00010100
~~~~~~~~
00000100       — rightmost set bit will tell us the position

## C++

Output:

20 in binary is 00010100
Position of the rightmost set bit is 3

Alternate Solution –

The idea is to negate n and perform bitwise AND operation with with itself i.e. (n & -n). Then the position of the rightmost set bit in n will be the position of the only set bit in the result. We can also use this hack for Problem 1. If (n & -n) == n, then given positive integer is a power of 2.

For example,

00…0010100  &                  (n = 20)
11…1101100                     (-n = -20)
~~~~~~~~~~
00…0000100

## C++

Output:

Position of the rightmost set bit is 3

Problem 3. Find position of the only set bit in a number

The idea is to unset the rightmost bit of number n and check if it becomes 0 or not. If it is non-zero, we know that there is another set bit present and we have invalid input. If it becomes 0, then the position of the only set bit can be found by processing every bit of n one by one or we can directly use log2(n) + 1.

For example, number 16 in binary is 00010000 and position of the rightmost set bit is 5.

00010000   &                   (n = 16)
00001111                       (n-1 = 15)
~~~~~~~~
00000000

log2(16) + 1 = 5

## C++

Output:

16 in binary is 00010000
Position of the only set bit is 5

Problem 4. Computing parity of a number (Naive solution)

“Parity” refers to the number of 1s in a given binary number. Odd parity(1) means there are an odd number of 1s and even parity(0) means that there are an even number of 1s. Parity bits are often used as a crude means of error detection as digital data is transmitted and received.

Naive solution would be to calculate parity by checking each bit of n one by one. The time taken is proportional to the number of bits in the number.

## C++

Output:

31 in binary is 00011111
Parity of 31 is odd

We can perform better by turn off rightmost set bit of the number one by one and count the parity. The below code uses an approach like Brian Kernigan’s bit counting. The time it takes is proportional to the number of bits set.

## C++

Output:

31 in binary is 00011111
Parity of 31 is odd

Another Solution: Compute parity of a number using lookup table

(1 votes, average: 5.00 out of 5)

Please use our online compiler to post code in comments. To contribute, get in touch with us.
Like us? Please spread the word and help us grow. Happy coding 🙂

These answers assume `(n & (n -1))` returns 0 only if n is a power of 2. It also returns 0 if n is 0.