Objective: Given a number, write and algorithm to find the right most set bit in it (In binary representation).
Example:
Number : 1 Binary representation: 1 Position of right most set bit: 1 Number : 6 Binary representation: 1 1 0 Position of right most set bit: 2 Number : 11 Binary representation: 1 0 1 1 Position of right most set bit: 1 Number : 24 Binary representation: 1 1 0 0 0 Position of right most set bit: 4
Approach:
If N is a number then the expression below will give the right most set bit.
N & ~ (N -1)
- Let’s dig little deep to see how this expression will work.
- We know that N & ~N = 0
- If we subtract 1 from the number, it will be subtracted from the right most set bit and that bit will be become 0.
- So if we negate the remaining number from step above then that bit will become 1.
- Now N & ~(N-1) will make all the bits 0 but the right most set bit of a number.
Example:
Say N =10, so N = 1 0 1 0, then ~N = 0 1 1 0 => N & ~ N =0 N – 1 = 1 0 1 0 – 0 0 0 1 = 1 0 0 1 ~(N-1) = 0 1 1 0 N & ~(N-1) = 0 0 1 0 => 2nd bit
Code:
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| public class RightMostSetBit { | |
| public static void findRightMostSetBit(int n){ | |
| double position = 1 + Math.log(n & ~(n–1))/Math.log(2); | |
| System.out.println("Right most set bit for " + n + " is : " + Integer.toBinaryString(n & ~(n–1))); | |
| System.out.println("Position: " + position); | |
| } | |
| public static void main(String[] args) { | |
| int n = 1; | |
| findRightMostSetBit(n); | |
| } | |
| } |
Output:
Right most set bit for 1 is : 1 Position: 1.0
The position for number 24 should be “4” not “3”.
Thanks for comment, corrected the line.