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)); | |
| } | |
| } |
Output:
Right most Unset bit :2.0