Right most set bit O(log N)

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.

• Your code seems to me O(logN), whats the problem exactly? Nov 22 '20 at 4:15
• @SerialLazer: Assuming n is an N bit number, the code is O(log n) = O(n). Nov 22 '20 at 10:40
• @natnav: "Competitive programming" doesn't pay the bill, and doesn't get you a job. And Mr. Arnav Kr. Mandal would be on my "do not hire" list for writing this abysmal code. Try it for n = 1, 2, 4, 8, 16 etc. and count how many results are correct. Nov 22 '20 at 10:46
• (@gnasher729: check the capitalisation of the last letter in your comment.) Nov 22 '20 at 14:15
• (an aspiring competitive programmer might want to know/mention int Integer.numberOfTrailingZeros​(int i).) Nov 22 '20 at 14:19

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

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.

• Just saying: The assumption that calculating log10(x) where x is an n-bit number can be done in constant time independent of n is quite laughable. Nov 22 '20 at 10:38
• @Pesudonym Thank you for the detailed explanation! It helped me a lot. Nov 22 '20 at 16:00

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;
}
• Why should numberOfTrailingZeros take time $O(log N)$? Also since Integer is a fixed-length type in java, technically any reasonable algorithm will have complexity $O(1)$. Nov 22 '20 at 16:46