Home > Mobile >  How can we decide that an integer is power of 2 by using bit manipulation?
How can we decide that an integer is power of 2 by using bit manipulation?

Time:09-15

For example if the given number n = 16 If it is power of 2 then the output should be true else false, i want the answer by using bit manipulation.

CodePudding user response:

Does this work? Source GeeksforGeeks:

def isPowerOfTwo(n):
    cnt = 0
    while n > 0:
        if n & 1 == 1:
            cnt = cnt   1
        n = n >> 1
 
    if cnt == 1:
        return 1
    return 0

# Driver code
if __name__ == "__main__":
 
    # Function call
    if(isPowerOfTwo(31)):
        print('Yes')
    else:
        print('No')
 
    if(isPowerOfTwo(64)):
        print('Yes')
    else:
        print('No')

Explanation:

All powers of 2 have only 1-bit set in them

Examples: 2 --> 10, 4 --> 100, 8 --> 1000, 16 --> 10000, so on

CodePudding user response:

The solution mentioned by @TimRoberts is the most simple way of using bit manipulation.

Just check if (n & (n - 1) == 0). Why does this work?

Assume n = 8 (1000 in base 2), then n - 1 = 7 (0111 in base 2). If you do a bitwise AND of these two, you get 0. This is true for n equal to any power of 2.

So you function should simply be:

bool is_power_of_2(unsigned long n)
{
    return (n & (n - 1)) == 0;
}
  • Related