Power of Two

Problem

Memory allocators require power-of-two block sizes for alignment, and hash tables resize to the next power of two to keep mod-hashing fast. Given an integer n, return True if n is an exact power of two (1, 2, 4, 8, ...) and False otherwise.

Input: n = 1  → True   (2^0)
Input: n = 8  → True   (2^3)
Input: n = 6  → False  (binary 110 has two set bits)
Input: n = 0  → False

Solution

Approach - Clear the lowest set bit with n & (n - 1).

A power of two has exactly one bit set: 1, 10, 100, 1000. The trick exploits what subtracting 1 does to such a number. n - 1 flips that single set bit to 0 and turns every bit below it into 1 - for example 8 = 1000 becomes 7 = 0111. ANDing the two together (n & (n - 1)) clears the original set bit and there are no other bits to survive, so the result is 0. For any number with two or more set bits, the higher bits are untouched by the subtraction and remain in the AND, so the result is non-zero. That gives the test (n & (n - 1)) == 0.

The n > 0 guard is essential. For n = 0, 0 - 1 in Python's arbitrary-precision two's complement is -1, an infinite string of 1s, and 0 & -1 = 0, which would falsely report 0 as a power of two. Negative inputs are also rejected by the guard since they are never powers of two. Trace n = 6 = 110: 6 - 1 = 5 = 101, and 110 & 101 = 100 = 4, which is non-zero, so the check correctly returns False.

Edge cases - n = 0 and negative n are handled by n > 0. n = 1 (which is 2^0) passes because 1 & 0 == 0.

Complexity - O(1) time, O(1) space - one subtraction and one AND, independent of the magnitude of n.