Right most set bit O(log N)

Question

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.

Answer 1

Questions about programming are off-topic, however there are a few computer science questions hidden in here: what n & -n does, and how floating point is represented.

The n & -n operation isolates the rightmost bit of a word in two's complement arithmetic. This is a very useful operation to know about.

Consider, for example, the following 8-bit word:

10010000

You can find the two's complement of this by taking the logical not of all the bits:

01101111

And then adding 1:

01110000

If you then take the logical and of this with the original word, you get:

00010000

This is the rightmost set bit of the original word. Please try a few examples for yourself to understand how this operation works.

Once you understand that, the rest is simply calculating base-2 logarithm of this number, essentially finding the highest/leftmost set bit, using an unnecessarily complicated method:

$$\log_2 x = \frac{\log_{10} x}{\log_{10} 2}$$

Quite apart from the fact that this is going to raise a floating point exception if you pass it zero (because what's $\log 0$?), and quite apart from the fact that the computational complexity of Math.log10 is not specified in the Java standard, floating-point numbers are stored in scientific notation in base-2 internally. The number $128.0$, for example, is stored as $1.0 \times 2^7$. So this is just an overly-complex way of extracting the exponent field of a floating-point number:

public static int getFirstSetBitPos(int n)
{
    return (int)Math.getExponent((float)(n & -n)) + 1;
}

The idea that you were probably supposed to have, however, is to use some kind of binary search. For a 32-bit integer, for example, you can tell if there is a set bit in the lowest-order 16 bits using a logical and with an appropriate mask:

(n & 0xFFFF) == 0

If there is a bit set in this range, then the answer to your question, the "find first set" of a number, is between 0 and 15, otherwise it's between 16 and 31. Either way, you have halved the search space. Turning this into an algorithm is left as an exercise.

Answer 2

I used @Pseudonym and @greybeard suggestions and came up with this solution.

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;
}