3

The problem asks to write a function that takes an integer as input and to return true if the integer is a power of two. I want to write my function using both the bitwise AND operator and logical shifting to practice these concepts. I tried to walk through many input examples and thought my code would work fine, but when Leetcode used a test case of "n=2", my code returned false instead of true.

My train of thought is that if the least significant bit ANDed with 1 equals to 0 (I'm trying to bitmask and only perform the AND operation on the n's LSB), then there is potential for n to be a power of 2. So I shift n one bit to the right, and evaluate if n is 1 (then yes, it's a power of 2, and return true to the function). If n is not 1, and the LSB ANDed with 1 is not 0, then that means n is definitely not a power of 2 - so I break out of the while loop and return false.

Can anyone help pinpoint what went wrong? 

bool isPowerOfTwo(int n){

    while(n>0)
    {
        if(n==1)
            return 1;

        else if(n&1 == 0)
            n = n>>1;

        else
            break;
    }
    return 0;
}
strawberryfields
  • 33
  • 3

1 Answers1

5

Your logic is correct. Unfortunately you fell into an operator precedence trap: == binds tighter than & due to ... history. n&1 == 0 is parsed as if n&(1 == 0) which naturally is always 0.

The fix is to use (n & 1) == 0.

Antti Haapala -- Слава Україні
  • 129,958
  • 22
  • 279
  • 321