This post is completed by 1 user

  • 1
 Add to List
Beginner

220. Find the right most unset bit OR zero bit of a number

Objective: Given a number, write an algorithm to find the right most unset bit or zero bit in it (In binary representation).

This problem is similar to Find the right most set bit of a number

Example:

Number : 11
Binary representation: 1 0 1 1
Position of right most unset bit: 2

Number : 6
Binary representation: 1 1 0
Position of right most unset bit: 0

Number : 13
Binary representation: 1 1 0 1
Position of right most unset bit: 1

Approach:

If N is a number then the expression below will give the right most unset bit.

~N &  (N +1)
  1. Let’s dig a little deep to see how this expression will work.
  2. We know that N & ~N = 0
  3. If we add 1 from the number, it will make the most unset bit to 1, if there are any set bits on the right side of the unset bit, that bit will become zero.
  4. (example : 1 0 1 1 + 0 0 0 1 = 1 1 0 0)
  5. So if we negate the original number it will make the rightmost unset bit to 1.
  6. Now ~N & (N+1) will make all the bits 0 but the right most unset bit of a number.

Example:

Say N =11, so N = 1 0 1 1
N + 1 = 1 1 0 0
~N = 0 1 0 1
~N & (N+1) = 0 1 0 0 => 2nd bit (assuming right-most index is 0)

Output:

Right most Unset bit :2.0

Related Problems: