Figuring out first set bit using O(log N)

help
, ,
1

I tried to do the problem Find first set bit in Geeks for Geeks, and this is the code I used.

public static int getFirstSetBitPos(int n){
    int counter = 0;
    while (n > 0){
        if ((n&1) == 1){
            return counter + 1;
        }
        n >>= 1;
        counter ++;
    }
    return 0; 
}

The problem asks to solve it in a time complexity of O(logN), and my code is O(N). When I looked at the editorial, it had this solution.

// Java Code for Position of rightmost set bit
class GFG {

    public static int getFirstSetBitPos(int n)
    {
        return (int)((Math.log10(n & -n)) / Math.log10(2)) + 1;
    }

    // Drive code
    public static void main(String[] args)
    {
        int n = 12;
        System.out.println(getFirstSetBitPos(n));
    }
}
// This code is contributed by Arnav Kr. Mandal

I don’t understand this return (int)((Math.log10(n & -n)) / Math.log10(2)) + 1; I would appreciate if someone could explain.

I am new to programming and an aspiring competitive programmer.

2

‘n’ will be equal to " n & -n ", if n is a power of two.
To understand this, you must know what is two’s complement of a binary number. Any negative integer is stored in the form of two’s complement of its corresponding positive value. Two’s complement is basically inverting all the bits and adding one to the resultant answer. Now that each and every bit has been inverted, the bits which were initially 1 now become 0. when you add 1 to the resultant number, the first zero from the left side gets changed back to one. Now when you find the bitwise and of the two numbers, you get the first set bit. Now all we have to do is take logarithm with base two of our answer and add one to it to get the set bit’s position from the left. Lets see this with an example.
Consider n=3 (011 in binary)
-n will be 100+1=101
n & -n = 001 , now we have the first set bit.
Consider n=12 (1100 in binary)
-n will be 0011+1=0100
n & -n = 0100
Hope this helps you!!

3

Thank you for helping, I was able to solve it. Here is my code.

public static int getFirstSetBitPos(int n){
    if (n == 0) return 0;
    if (n%2 == 1) return 1;
    return Integer.numberOfTrailingZeros((int) ((n & -n)+1) & n) + 1;
}

I also got help from this algorithms - Right most set bit O(log N) - Computer Science Stack Exchange

4

BTW your initial solution takes O(\log_{2}{n}) time, not O(n) time.

5

@ankushkhanna Thank you for pointing that out I appreciate it.

1 Like