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 2. Find position of the rightmost set bit

**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++

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 |
#include <iostream> #include <bitset> using namespace std; // returns position of the rightmost set bit of n int rightmostSetBitPos(int n) { // if number is odd, return 1 if (n & 1) return 1; // unset rightmost bit and xor with number itself n = n ^ (n & (n - 1)); // cout << bitset<8>(n) << endl; // find the position of the only set bit in the result // we can directly return log2(n) + 1 from the function int pos = 0; while (n) { n = n >> 1; pos++; } return pos; } // main function int main() { int n = 20; cout << n << " in binary is " << bitset<8>(n) << endl; cout << "Position of the rightmost set bit is " << rightmostSetBitPos(n); return 0; } |

`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++

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
#include <iostream> #include <math.h> using namespace std; // returns position of the rightmost set bit of n int rightmostSetBitPos(int n) { // if number is odd, return 1 if (n & 1) return 1; return log2(n & -n) + 1; } // main function int main() { int n = 20; cout << "Position of the rightmost set bit is " << rightmostSetBitPos(n); return 0; } |

`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++

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 |
#include <iostream> #include <bitset> #include <math.h> using namespace std; // returns position of the only set bit of n int setBitPos(int n) { // unset rightmost bit and check if the number is non-zero if (n & (n - 1)) { cout << "Wrong input"; return 1; } return log2(n) + 1; } // main function int main() { int n = 16; cout << n << " in binary is " << bitset<8>(n) << endl; cout << "Position of the only set bit is " << setBitPos(n); return 0; } |

`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++

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 |
#include <iostream> #include <bitset> using namespace std; // find parity of number n unsigned findParity(unsigned n) { bool parity = false; // run till n is not zero while (n) { // invert the parity flag if (n & 1) parity = !parity; // right shift n by 1 (divide by 2) n = n >> 1; } return parity; } // main function int main() { unsigned n = 31; cout << n << " in binary is " << bitset<8>(n) << endl; if (findParity(n)) cout << "Parity of " << n << " is odd"; else cout << "Parity of " << n << " is even"; return 0; } |

`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++

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 |
#include <iostream> #include <bitset> using namespace std; unsigned findParity(unsigned n) { bool parity = false; // run till n is not zero while (n) { // invert the parity flag parity = !parity; // turn off rightmost set bit n = n & (n - 1); } return parity; } // main function int main() { unsigned n = 31; cout << n << " in binary is " << bitset<8>(n) << endl; if (findParity(n)) cout << "Parity of " << n << " is odd"; else cout << "Parity of " << n << " is even"; return 0; } |

`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

These answers assume

`(n & (n -1))`

returns 0 only if n is a power of 2. It also returns 0 if n is 0.In problem 1, it is given that we don’t have to use branch statements. But in the solution, “if” conditional statement is used. That’s wrong right?

Thanks for sharing your concerns. Could you have another look – https://ideone.com/5IuA3I

We’re not using if any conditional statement. Maybe you’re referring to problem #2?