Power of two check

Decide whether a number is a power of two with a single AND, no loop or log needed.

The idea

A power of two has exactly one set bit, like 01000000. Subtracting 1 flips that single bit to 0 and turns every bit below it to 1, like 00111111. ANDing the two values together then leaves nothing in common, so the result is 0 only when n started with a single set bit.

Code

public static bool IsPowerOfTwo(int n) {
    if (n <= 0) return false;
    int m = n - 1;
    int r = n & m; // clears the lowest set bit, if any
    return r == 0;
}

Tips

• This is the same n & (n - 1) trick used to clear the lowest set bit in Count set bits.
• Remember the n <= 0 guard: 0 and negative numbers are never powers of two, even though 0 & -1 happens to be 0.

In the .NET library

If n has more than one set bit, n & (n - 1) only clears the lowest one and leaves the rest, so the result is never 0. That is what makes this test exact.