cmathbit-manipulation

How does this bitwise operation check for a power of 2?

Here's a condition that checks if a number is a power of 2 using the following:

if((num != 1) && (num & (num - 1))) { /* make num pow of 2 */ }

My question is, how does using a bitwise AND between num and num - 1 determine if a number is a power of 2?

Solution

  • Any power of 2 minus 1 is all ones: (2 N - 1 = 111....b)

    2 = 2^1.  2-1 = 1 (1b)
4 = 2^2.  4-1 = 3 (11b)
8 = 2^3.  8-1 = 7 (111b)

    Take 8 for example. 1000 & 0111 = 0000

    So that expression tests if a number is NOT a power of 2.