Bit Manipulation

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

by

Objective: Given a number, write and 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)
  • Let’s dig little deep to see how this expression will work.
  • We know that N & ~N = 0
  • If we add 1 from the number, it will make most unset bit to 1, if there are any set bits in the right side of unset bit, those bit will become zero.
  • (example : 1 0 1 1 + 0 0 0 1 = 1 1 0 0)
  • So if we negate the original number it will make the right most unset bit to 1.
  • 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)

Code:


public class RightMostUnsetBit {
public static double getRightMostUnsetBit(int n){
if(n==1)
return –1;
return Math.log(~n & (n+1))/Math.log(2);
}
public static void main(String[] args) {
int n = 11;
System.out.println("Right most Unset bit :" + getRightMostUnsetBit(n));
}
}

view raw

RightMostUnsetBit.java

hosted with ❤ by GitHub

Output:

Right most Unset bit :2.0

Related Posts: