3
$\begingroup$

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.

$\endgroup$
8
  • $\begingroup$ Your code seems to me O(logN), whats the problem exactly? $\endgroup$ Nov 22 '20 at 4:15
  • 1
    $\begingroup$ @SerialLazer: Assuming n is an N bit number, the code is O(log n) = O(n). $\endgroup$
    – gnasher729
    Nov 22 '20 at 10:40
  • $\begingroup$ @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. $\endgroup$
    – gnasher729
    Nov 22 '20 at 10:46
  • $\begingroup$ (@gnasher729: check the capitalisation of the last letter in your comment.) $\endgroup$
    – greybeard
    Nov 22 '20 at 14:15
  • 2
    $\begingroup$ (an aspiring competitive programmer might want to know/mention int Integer.numberOfTrailingZeros​(int i).) $\endgroup$
    – greybeard
    Nov 22 '20 at 14:19
4
$\begingroup$

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.

$\endgroup$
2
  • 1
    $\begingroup$ 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. $\endgroup$
    – gnasher729
    Nov 22 '20 at 10:38
  • $\begingroup$ @Pesudonym Thank you for the detailed explanation! It helped me a lot. $\endgroup$
    – nat nav
    Nov 22 '20 at 16:00
2
$\begingroup$

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;
}
$\endgroup$
1
  • 1
    $\begingroup$ 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)$. $\endgroup$
    – Steven
    Nov 22 '20 at 16:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.