How (x & (x - 1)) == 0 Checks for Powers of Two

In binary computation, the bitwise expression (x & (x - 1)) == 0 is an efficient, constant-time method used to verify whether a positive integer x is a power of two. This technique works by leveraging the unique binary structure of powers of two—which always consist of a single 1 bit followed exclusively by 0s—and observing how subtracting 1 alters that bit pattern to cancel out shared bits during a bitwise AND operation.

Binary Structure of Powers of Two

In the binary system, every power of two (\(2^0, 2^1, 2^2, 2^3, \dots\)) contains exactly one bit set to 1, with all other lower-order bits set to 0:

Any positive integer that is not a power of two contains two or more bits set to 1 (for example, \(6 = 0110_2\) or \(12 = 1100_2\)).

What Happens During (x - 1)

Subtracting 1 from any binary number flips the lowest set bit (the rightmost 1) to 0, and turns all the trailing 0 bits to its right into 1s.

When x is a power of two: * There is only one 1 bit in the entire number. * Subtracting 1 turns that single 1 bit into a 0. * All bits to the right of that position become 1s.

For example, when \(x = 8\): * \(x = 8 = 1000_2\) * \(x - 1 = 7 = 0111_2\)

The Bitwise AND Operation (&)

The bitwise AND (&) operator compares each corresponding bit of two numbers. It returns a 1 only if both bits are 1; otherwise, it returns 0.

When you perform x & (x - 1) on a power of two: * The position that held a 1 in x now holds a 0 in (x - 1). * The positions that hold 1s in (x - 1) held 0s in x.

Because x and (x - 1) share no matching 1 bits at the same index, every column results in 0:

    1000_2  (8)
  & 0111_2  (7)
  --------
    0000_2  (0)

Since the result is 0, the condition (x & (x - 1)) == 0 evaluates to true.

Non-Powers of Two

If x is not a power of two, it has more than one set bit. Subtracting 1 only modifies the rightmost 1 bit and the bits after it; any higher-order 1 bits remain untouched.

For example, when \(x = 6\): * \(x = 6 = 0110_2\) * \(x - 1 = 5 = 0101_2\)

Evaluating 6 & 5:

    0110_2  (6)
  & 0101_2  (5)
  --------
    0100_2  (4)

Because the higher-order 1 bit remains in both operands, the result is 4 (non-zero), and the condition (x & (x - 1)) == 0 evaluates to false.

Summary

The expression works because x - 1 clears the lowest set bit of x and sets all lower bits. Performing a bitwise AND between x and x - 1 removes the lowest set bit from x. If x is a positive power of two, removing its only set bit leaves behind all zeros, producing a result of 0.