This is a classical interview question in which you are asked to find the location of the rightmost and the leftmost 1’s in the binary representation of a number.
I. Rightmost Set Bit & Rightmost Bit
Here we compute the AND between the original number (say N) with its two’s complement (its negative form). Thus, rightmost set = N & (~N + 1) or rightmost set = N & ~(N – 1). Then we do a log2 on the result and round up by 1.
import java.io.*;
class GFG {
public static int getFirstSetBitPos(int n)
{
return (int)((Math.log10(n & -n)) / Math.log10(2)) + 1;
}
}
// This code is contributed by Arnav Kr. Mandal
Or, we use shift.
import java.util.*;
public class Solution {
public static int rightmostSetBit(int n){
int position = 1;
// m variable is used to check the set bit
int m = 1;
while ((n & m) == 0) {
// Perform left shift
m = m << 1;
position++;
}
return position;
}
II. Leftmost Set Bit
Simply shift N to left one bit at a time until N <= 0.
import java.util.*;
public class Solution {
public static int leftmostSetBit(int n){
// Initializing the position bit to 1
int pos = 0;
while (n > 0) {
n = n >> 1;
pos++;
}
return pos;
}
Resources:
Si Qi Cao 