Power of Two

Complexity Analysis

Time Complexity O(1) Space Complexity O(1)

Time Complexity: O(1)

Breakdown

Subtraction n - 1: single CPU instruction
Bitwise AND n & (n-1): single CPU instruction
Comparison with zero: single CPU instruction
Total: 3-4 machine instructions

T(n) = O(1) — constant time, independent of n

Mathematical Intuition

Powers of two have exactly one bit set: 2^k = 1 followed by k zeros. Subtracting 1 flips all bits from the rightmost set bit down: n - 1 changes 100...0 to 011...1. The AND of these shares no common bits, yielding zero. For non-powers, at least one higher bit survives.

Key Insight

The operation n & (n-1) clears the rightmost set bit. This technique is foundational in bit manipulation (e.g., counting set bits, finding lowest set bit).

Space Complexity: O(1)

Breakdown

Input stored in a single register
Intermediate n - 1: one register
Result of AND: one register
No heap allocation or data structures

S(n) = O(1) — fixed number of registers

Mathematical Intuition

Bit manipulation operates on fixed-width integers (32 or 64 bits). The space used is independent of the numeric value—a 64-bit integer uses 8 bytes whether it holds 1 or 2⁶³. No auxiliary data structures are needed.

Key Insight

Alternative approaches (loop counting bits, division by 2) use O(log n) time. The bit trick achieves O(1) by exploiting binary representation properties.

n

n - 1

Current Bit

Result

Time Complexity: O(1)

Space Complexity: O(1)