How would you check if a number is a power of 2 using bit manipulation?

If a number is a power of 2, it has one set bit in its binary representation and all other bits are unset.

Here is the binary representation of powers of 2:

$$\begin{aligned} 2^0 & = 1 & = 0001\_b \\ 2^1 & = 2 & = 0010\_b \\ 2^2 & = 4 & = 0100\_b \\ 2^3 & = 8 & = 1000\_b \\\end{aligned}$$

As you can see, these binary representations only have one bit set (one ’1’) and the rest are zeroes. This is a defining characteristic of powers of 2.

We can express this characteristic using bit manipulation. If ‘n‘ is a power of 2, then ‘n‘ AND ‘n-1‘ will be ‘0‘.

Let’s examine this. If ‘n‘ is a power of 2, we have a binary representation like ‘1000...0‘. Now, ‘n-1‘ will be ‘0111...1‘. When we do a bitwise AND operation (‘&‘), every bit of the result will be ‘0‘ because ‘1‘ AND ‘0‘ yields ‘0‘ and ‘0‘ AND ‘1‘ also yields ‘0‘.

More formally, let’s represent the number as 2^k. Then the binary representation of 2^k in a sufficiently large number of bits is:

2^k = 1000...0

And 2^k − 1 is:

2^k − 1 = 0111...1

So, the bitwise AND of these two numbers:

2^k&(2^k − 1) = 0000...0 = 0

You can implement this as a function in any language that supports bitwise operations. For example, in Java:

boolean isPowerOfTwo(int n) {
  if(n <= 0) return false;
  return (n & (n - 1)) == 0;
}

This function first checks if the number is positive (since the method doesn’t work for negatives or zero), then it returns whether ‘n & (n - 1) == 0‘. If ‘n‘ is power of 2, this will be ‘true‘, otherwise ‘false‘.