Power of Two Check: Bitwise Algorithm Deep Dive

1. Introduction and Core Concepts

The power of two check is a fundamental bit manipulation technique that determines whether a given integer can be expressed as 2ⁿ for some non-negative integer n. In other words, it answers whether a number belongs to the sequence 1, 2, 4, 8, 16, 32, 64, 128, and so on. While this may seem like a trivial mathematical question, its efficient solution lies at the heart of low-level computing, where binary representation governs performance.

At its core, the power of two check leverages the unique binary structure of powers of two. Every power of two in binary has exactly one bit set to 1 and all other bits set to 0. For example, 1 is 0001, 2 is 0010, 4 is 0100, and 8 is 1000. This property is not shared by any other positive integer, which will always have either zero bits set (the number 0) or two or more bits set (like 3 = 0011 or 6 = 0110). Recognizing this pattern allows us to replace expensive arithmetic operations like division or logarithms with a single, lightning-fast bitwise operation.

Understanding the power of two check matters far beyond academic curiosity. Modern computer systems are built on binary foundations, and many critical subsystems require buffer sizes, memory alignments, hash table capacities, and network packet sizes to be powers of two for optimal performance. Operating systems, graphics engines, database allocators, and high-frequency trading systems all depend on quickly validating this property. A naive approach using loops or floating-point math can introduce subtle bugs and performance bottlenecks, whereas the bitwise algorithm provides a constant-time, branch-predictable, and elegant solution that every serious software engineer should master.

Why Powers of Two Are Special in Computing

Computers operate on binary, and powers of two align perfectly with how hardware addresses memory. When an array size or memory block is a power of two, address calculations can be performed with bit shifts instead of multiplication, and modulo operations can be replaced with bitwise AND masks. This is why many allocators round up requests to the next power of two and why hash tables often resize to powers of two.

Furthermore, powers of two simplify binary arithmetic. Multiplying or dividing by a power of two is equivalent to shifting bits left or right, which is one of the fastest operations a CPU can execute. Validating this property efficiently therefore becomes a building block for higher-level optimizations in compilers, virtual machines, and embedded systems.

2. How It Works

The classic bitwise power of two check relies on the expression n & (n - 1) == 0. To understand why this works, we must examine what subtracting one does to a binary number. When you subtract 1 from any positive integer, you flip all the bits from the rightmost set bit (the lowest 1) down to the least significant bit. For example, if n = 8 (1000), then n - 1 = 7 (0111). If n = 12 (1100), then n - 1 = 11 (1011).

For a power of two, there is only a single 1 bit. Subtracting 1 flips that bit to 0 and turns all lower bits to 1. Consequently, n and n - 1 have no overlapping 1 bits at all. Their bitwise AND is therefore exactly zero. For any non-power-of-two, there are at least two 1 bits, and subtracting 1 will leave the higher set bits unchanged. The AND operation will then preserve at least one common 1 bit, resulting in a non-zero value.

This insight leads to the canonical condition: a positive integer n is a power of two if and only if (n & (n - 1)) == 0. However, this condition alone is insufficient because it also holds for n = 0 (since 0 & -1 == 0). Therefore, a complete check must also verify that n is greater than zero. The final, correct predicate is n > 0 and (n & (n - 1)) == 0.

The Binary Anatomy of n and n-1

Consider n = 16, which is 10000 in binary. Then n - 1 = 15, which is 01111. Aligning them: 10000 & 01111 = 00000. The result is zero, confirming a power of two. Now consider n = 18, which is 10010. Then n - 1 = 17, which is 10001. Their AND is 10000, which is non-zero, correctly rejecting the number. This pattern holds universally because the operation isolates the lowest set bit and clears it.

An alternative perspective uses the property n & -n, which isolates the lowest set bit due to two's complement representation. For a power of two, n & -n == n, because the only set bit is also the lowest set bit. While correct, this variant requires handling signed integer representation carefully and is slightly less idiomatic than the n & (n - 1) trick.

Mathematical Foundation

Mathematically, the set of powers of two corresponds to numbers with Hamming weight (population count) equal to 1. The operation n & (n - 1) is known as the Brian Kernighan's algorithm step, which clears the lowest set bit. If a number has exactly one set bit, clearing it yields zero. If it has more than one, clearing one still leaves at least one bit set. Thus, the check is essentially a population count test optimized to a single operation.

3. Implementation

Implementing the power of two check in Python is straightforward, but robust implementations must account for edge cases, type constraints, and Python's arbitrary-precision integers. Below are several canonical implementations with detailed comments.

def is_power_of_two_bitwise(n: int) -> bool:
    """
    Classic bitwise power of two check.
    Returns True if n is a power of two, False otherwise.
    """
    # Powers of two are strictly positive. 0 and negatives are rejected.
    if n <= 0:
        return False
    # n & (n - 1) clears the lowest set bit.
    # If result is 0, n had exactly one bit set.
    return (n & (n - 1)) == 0

# Test cases
print(is_power_of_two_bitwise(1))    # True  -> 2^0
print(is_power_of_two_bitwise(16))   # True  -> 2^4
print(is_power_of_two_bitwise(18))   # False
print(is_power_of_two_bitwise(0))    # False
print(is_power_of_two_bitwise(-8))   # False

def is_power_of_two_iterative(n: int) -> bool:
    """
    Naive iterative approach for comparison.
    Repeatedly divides by 2. Useful for understanding but not optimal.
    """
    if n <= 0:
        return False
    # Keep dividing by 2 while divisible
    while n % 2 == 0:
        n //= 2
    # If we end at 1, original was a power of two
    return n == 1

def is_power_of_two_log(n: int) -> bool:
    """
    Logarithm-based approach. Demonstrates floating-point pitfalls.
    """
    import math
    if n <= 0:
        return False
    # log2(n) should be an integer for powers of two
    # Use is_integer() to avoid floating point errors where possible
    log_val = math.log2(n)
    return log_val.is_integer()

# Floating point failure example: large power of two may not be exact
print(is_power_of_two_log(2**53 + 1))  # Potential false positive/negative

def is_power_of_two_popcount(n: int) -> bool:
    """
    Population count (Hamming weight) variant.
    Uses Python 3.8+ int.bit_count() (Python 3.10+).
    More explicit but slightly slower than n & (n-1).
    """
    if n <= 0:
        return False
    # bin(n).count('1') works on all versions, bit_count() is faster
    # For compatibility, we show both
    try:
        return n.bit_count() == 1  # Python 3.8+ with int.bit_count in 3.10
    except AttributeError:
        return bin(n).count('1') == 1

def is_power_of_two_lowbit(n: int) -> bool:
    """
    Alternative using n & -n to isolate lowest set bit.
    n & -n == n iff n is a power of two (and n != 0).
    """
    if n <= 0:
        return False
    return (n & -n) == n

def next_power_of_two(n: int) -> int:
    """
    Extension: Find the smallest power of two >= n.
    Useful for allocators and hash table resizing.
    Uses bit manipulation to fill all bits below highest set bit.
    """
    if n <= 0:
        return 1
    if is_power_of_two_bitwise(n):
        return n
    # Decrement to handle exact powers correctly, then spread highest bit
    n -= 1
    n |= n >> 1
    n |= n >> 2
    n |= n >> 4
    n |= n >> 8
    n |= n >> 16
    n |= n >> 32  # Needed for 64-bit numbers; Python handles larger automatically
    # For arbitrary precision, loop until shift covers all bits
    # while (n >> shift) > 0: n |= n >> shift; shift *= 2
    return n + 1

print(next_power_of_two(19))  # 32
print(next_power_of_two(64))  # 64

4. Step-by-Step Example

Let us walk through the bitwise check in detail for two concrete numbers: 32 (which is a power of two) and 22 (which is not). We will examine their 8-bit binary representations to make the operation visually clear. Understanding this walkthrough is key to internalizing why the trick works and to debugging it when applied in larger systems.

First, consider n = 32. In binary, 32 is represented as 00100000 (2⁵). To compute n - 1, we subtract 1, which yields 31, or 00011111 in binary. Notice how the single 1 at position 5 has become 0, and all bits to its right have become 1. Now we perform the bitwise AND: 00100000 & 00011111. Comparing each column, there is no position where both numbers have a 1, so the result is 00000000, which is 0. Since n is positive and the result is zero, the algorithm correctly returns True.

Now consider n = 22. In binary, 22 is 00010110 (16 + 4 + 2). Subtracting 1 gives 21, which is 00010101. Let us align them: 00010110 (22) and 00010101 (21). Performing the AND operation bit by bit: 00010110 & 00010101 = 00010100, which is 20 in decimal and non-zero. The result is non-zero because the higher set bits (the 16's place) remained unchanged after subtracting 1, so they still overlap. The algorithm therefore correctly returns False, indicating 22 is not a power of two.

Edge Case Walkthrough: n = 0 and n = 1

The edge cases reveal why the n > 0 guard is essential. For n = 0 (00000000), n - 1 in two's complement wraps to all 1s (11111111 for 8-bit, or -1 conceptually). Then 00000000 & 11111111 = 00000000. Without the positivity check, 0 would be incorrectly classified as a power of two. For n = 1 (00000001), n - 1 = 0 (00000000), and 00000001 & 00000000 = 00000000, correctly returning True since 2⁰ = 1 is indeed a power of two.

For negative numbers, Python's infinite-precision two's complement representation means n & (n - 1) can behave unexpectedly if the guard is omitted. For example, n = -8 in Python is not just 8 bits but an infinite series of leading ones. The check n <= 0 immediately rejects negatives, avoiding any reliance on fixed-width assumptions and ensuring mathematical correctness.

5. Complexity Analysis

The bitwise power of two check is celebrated precisely because of its exceptional complexity characteristics. Unlike iterative or logarithmic approaches, it executes in constant time and constant space regardless of input size, making it ideal for hot paths in performance-critical code.

Time complexity is O(1). The operation consists of a single subtraction, a single bitwise AND, and a single comparison. On modern CPUs, these are all single-cycle instructions that operate on a full machine word (32 or 64 bits) simultaneously. There are no loops, no branches beyond the initial positivity check, and no memory accesses. Even in Python, where integers have arbitrary precision, the operation is O(number of machine words) which for practical purposes (numbers fitting in 64 bits) is effectively constant. For extremely large integers with thousands of bits, the cost scales with the number of limbs, but this is rarely relevant.

Space complexity is O(1) as well. The algorithm uses only a few integer variables and does not allocate any auxiliary data structures, recursion stacks, or buffers. It operates entirely in registers. This contrasts sharply with approaches that convert the number to a string or binary representation, which would require O(log n) space.

Best, average, and worst cases are identical for the bitwise method because the number of operations does not depend on the input value. Whether n is 1, 1,048,576, or 1,073,741,823, the same three operations are performed. This predictability is crucial for real-time systems and for avoiding timing side-channels in cryptographic code where variable-time operations could leak information.

*Population count is O(1) for fixed-width integers in hardware (POPCNT instruction), but O(number of words) for arbitrary-precision Python ints. The logarithm method, while O(1), suffers from floating-point precision issues and is significantly slower due to FPU involvement.

6. Variations and Optimizations

While the basic n & (n - 1) check is optimal for a single query, several variations and optimizations exist for specialized contexts, such as bulk checking, compile-time evaluation, or constrained environments without bitwise operations.

One common optimization is to combine the positivity and power-of-two check into a branchless form for vectorized code. For example, in C or NumPy, you might compute (n != 0) && ((n & (n - 1)) == 0) in a way that avoids branching. In Python, the short-circuit n > 0 and (n & (n - 1)) == 0 is already optimal because Python's interpreter overhead dominates.

Another variation checks for powers of four or powers of eight by adding a mask. A power of four is a power of two where the single set bit is in an even position (0, 2, 4...). Thus, n > 0 and (n & (n - 1)) == 0 and (n & 0x55555555) != 0 checks for powers of four. The mask 0x55555555 is 0101... in binary, selecting even positions. Similarly, powers of two can be distinguished by modulo properties, but bit masks are far faster.

For finding the next power of two, the bit-smearing technique shown in the implementation section is the standard optimization. It works by propagating the highest set bit to all lower positions and then adding one. This runs in O(log word size) shifts, typically 5-6 operations for 32/64-bit numbers, and is vastly faster than looping and multiplying by two. Compilers often provide intrinsics like __builtin_clz (count leading zeros) to implement this in 2-3 instructions.

Vectorized and Parallel Checks

When checking many numbers at once, such as validating an array of buffer sizes, vectorization using NumPy or SIMD instructions can apply the bitwise check to 4-8 integers simultaneously. In NumPy, (arr > 0) & ((arr & (arr - 1)) == 0) operates on entire arrays without Python loops, achieving near-C speed. In hardware, GPUs can perform this check for thousands of threads in parallel.

For cryptographic or safety-critical code, a constant-time variant is preferred to prevent timing attacks. The branch if n <= 0 could leak information via branch prediction. A branchless version might be ((n - 1) & ~n) >> (word_size - 1) or simply rely on the fact that the bitwise operation itself is constant-time and handle zero separately with arithmetic masking.

7. Real-World Applications

The power of two check is not an abstract puzzle; it is embedded in the infrastructure of modern computing. Its applications span systems programming, web infrastructure, data management, and digital media.

In memory management, allocators like jemalloc, tcmalloc, and the Linux buddy system allocate memory in power-of-two sized blocks. This reduces external fragmentation and allows coalescing of free blocks using simple bitwise operations. Before allocating, the allocator must verify that a requested block size is valid or round it up to the next power of two. The check ensures alignment requirements for SIMD instructions (which often require 16, 32, or 64-byte alignment) are met, preventing segmentation faults and performance penalties.

In web servers and databases, hash tables and ring buffers frequently use power-of-two capacities. When a hash table's size is a power of two, the modulo operation hash % capacity can be replaced with hash & (capacity - 1), which is an order of magnitude faster. Nginx, Redis, and PostgreSQL all use this optimization. Resizing logic must therefore ensure the new capacity remains a power of two, and the check is used in assertions and configuration validation.

In networking, packet sizes, buffer rings, and sequence number spaces are often powers of two to simplify wrap-around logic. For example, a circular buffer of size 1024 can use index & 1023 to wrap indices without branching. Graphics processing relies heavily on power-of-two textures (e.g., 256x256, 512x512) because mipmapping and texture compression algorithms assume these dimensions. OpenGL historically required power-of-two textures, and while modern APIs relax this, the performance advantage remains, so asset pipelines validate dimensions with this check.

8. Comparison with Alternatives

Several alternative methods can determine if a number is a power of two, each with distinct trade-offs in performance, correctness, and readability. Understanding these alternatives helps in choosing the right tool for interviews, production code, and educational contexts.

The iterative division method repeatedly divides n by 2 until it becomes odd. It is intuitive and easy to prove correct, but it requires O(log n) divisions, which are among the slowest integer operations. It also fails to exploit the binary nature of the problem and is unsuitable for hot paths.

The logarithm method computes log2(n) and checks if it is an integer. While mathematically elegant, it introduces floating-point inaccuracies. For large integers beyond 2⁵³, double-precision floats cannot represent all integers exactly, leading to false positives or negatives. It also requires importing math and invoking the FPU, making it 10-100x slower than the bitwise method.

The population count method counts the number of 1 bits using bin(n).count('1') or bit_count(). It is explicit and self-documenting, but it involves string conversion or a loop over bits, making it slower than the single AND operation. However, on CPUs with a dedicated POPCNT instruction, it can be competitive and is arguably more readable for beginners.

The brute-force lookup method precomputes all powers of two up to a limit and checks membership via a set. This is O(1) with a hash lookup and is useful when the domain is small and fixed (e.g., checking if a texture size is valid among 8, 16, 32...4096). But it does not scale to arbitrary integers and wastes memory.

*Logarithm is theoretically O(1) but practically slower and imprecise. For production code, the bitwise method is almost always preferred unless readability for non-systems programmers is the primary concern, in which case popcount with a clear function name is a defensible choice.

9. Common Mistakes and Best Practices

Despite its simplicity, the power of two check is a frequent source of subtle bugs, especially in interviews and in code that must handle untrusted input. Awareness of these pitfalls separates robust systems code from fragile scripts.

The most common mistake is forgetting the positivity check. Writing (n & (n - 1)) == 0 alone incorrectly returns True for n = 0. In many contexts, 0 is not a power of two, and treating it as such can cause division-by-zero errors later (e.g., when using n - 1 as a mask). Always write n > 0 and (n & (n - 1)) == 0. Some codebases explicitly check n != 0 instead of n > 0, but this incorrectly accepts negative powers of two in languages with two's complement wrap-around, so the strict greater-than is safer.

A second mistake is using floating-point logarithms without considering precision. Code like math.log2(n) % 1 == 0 or 2 ** round(math.log2(n)) == n will fail for large n due to rounding. If you must use logarithms, use Decimal or verify by reconstructing the power with integer arithmetic: 1 << round(math.log2(n)) == n, but even then, prefer bitwise.

A third pitfall is operator precedence. In Python and C, & has lower precedence than ==, so n & n - 1 == 0 is parsed as n & (n - 1 == 0), which is completely wrong. Always parenthesize: (n & (n - 1)) == 0. This bug is insidious because it may pass some tests while failing others.

Best Practices

First, encapsulate the check in a well-named function like is_power_of_two rather than inlining the bitwise trick everywhere. This improves readability and centralizes the edge-case handling. Add a docstring that explicitly states that 0 and negatives return False.

Second, add type hints and input validation. In Python, ensure the input is an int; floats should be rejected or explicitly converted. In statically typed languages, use unsigned integers when possible to eliminate the negative case entirely.

Third, use assertions in performance-critical code to validate assumptions early. For example, before using capacity - 1 as a mask, assert is_power_of_two(capacity) so failures are caught during testing rather than as silent data corruption in production. Finally, when writing portable code, be mindful of Python's arbitrary-precision integers versus fixed-width integers in C/Rust; the algorithm works for both, but the next-power-of-two smearing logic must be adapted for word size.

10. Interview Questions

Power of two checks are a staple of technical interviews because they test bit manipulation fundamentals, edge-case reasoning, and the ability to optimize. Below are common questions and how to approach them effectively.

Q1: Write a function to check if a number is a power of two.

This is the baseline question. The expected answer is the bitwise solution with the positivity guard. Start by stating the binary property (exactly one bit set), then write return n > 0 and (n & (n - 1)) == 0. Mention the O(1) time and O(1) space complexity and explain why you check n > 0. Bonus points for mentioning the alternative n & -n == n and discussing operator precedence.

Q2: How would you check if a number is a power of four? Or power of eight?

This tests extension of the core idea. For power of four, you need two conditions: it must be a power of two, and its single set bit must be in an even position. The solution is n > 0 and (n & (n - 1)) == 0 and (n & 0x55555555) != 0. Explain that 0x55555555 is 010101... in binary. For power of eight, the set bit must be at position 0, 3, 6..., so you would use mask 0x49249249 (001001001...). Alternatively, you can check n > 0 and (n & (n - 1)) == 0 and n % 3 == 1 for power of four, since powers of four modulo 3 are always 1, but the bit mask is faster and more general.

Q3: Given an integer, find the next power of two greater than or equal to it. Do it without loops if possible.

This evaluates ability to manipulate bits beyond a simple check. The optimal solution is the bit-smearing method: decrement n, then repeatedly OR with right-shifted versions (1, 2, 4, 8, 16, 32), then increment. Explain that this propagates the highest set bit to fill all lower bits, and adding one yields the next power of two. Mention the edge case where n is already a power of two and the need to handle n <= 0. For Python, note that arbitrary precision requires a loop over shifts until the shift covers the bit length.

Q4: Count how many numbers in an array are powers of two. Optimize for large arrays.

Here the interviewer looks for vectorization and performance awareness. The naive loop calls is_power_of_two for each element, which is O(m) for m elements. The optimized Python solution uses NumPy: np.sum((arr > 0) & ((arr & (arr - 1)) == 0)), which is vectorized in C and avoids Python loop overhead. Discuss trade-offs: NumPy has overhead for small arrays but wins for large ones. Also mention that if the array is sorted, you could binary search, but the bitwise check is so cheap that linear scan is usually fine.

Q5: Why does n & (n - 1) clear the lowest set bit? Prove it.

This is a deeper theory question. Provide a proof by considering binary representation: let n = ...1000 (with k trailing zeros). Then n - 1 = ...0111. The AND clears the lowest 1 and all trailing zeros remain zero, while higher bits are unchanged except the lowest 1 becomes 0. Formally, if n = a * 2^k where a is odd, then n - 1 = a * 2^k - 1 = (a-1)*2^k + (2^k -1), and the bitwise AND isolates the higher part. This property is the basis for Brian Kernighan's algorithm to count set bits by repeatedly applying n &= n - 1 until n becomes zero, with the count of iterations equal to the population count.