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

 
Download   Run Code
 


 
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

 
Download   Run Code
 



 
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++ implementation –
 

Download   Run Code

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++ implementation –
 

Download   Run Code

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++ implementation –
 

Download   Run Code

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++ implementation –
 

Download   Run Code

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++ implementation –
 

Download   Run Code

Output:

31 in binary is 00011111
Parity of 31 is odd

 
Another Solution: Compute parity of a number using lookup table

 
Read More –

Bit Hacks – Part 1 (Basic)
Bit Hacks – Part 2 (Playing with k’th bit)
Bit Hacks – Part 4 (Playing with letters of English alphabet)
Bit Hacks – Part 5 (Find absolute value of an integer without branching)
Bit Hacks – Part 6 (Random Problems)

 
Suggested Read: https://graphics.stanford.edu/~seander/bithacks.html

 
Thanks for reading.




Please use ideone or C++ Shell or any other online compiler link to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂
 





Leave a Reply

Notify of
avatar
Sort by:   newest | oldest | most voted
Keith
Keith

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

wpDiscuz