Power of Two — Solution

Problem

Given an integer, determine whether it equals 2^k for some non-negative integer k — that is, whether it belongs to the sequence 1, 2, 4, 8, 16, ….

• Input: n = 16
• Output: true
• Explanation: 16 = 2^4, so it is a power of two.

Counter-example: n = 6 → false, because 6 = 2 × 3 and cannot be written as a pure power of two.

Intuition

Every power of two has exactly one set bit in binary — 16 looks like 10000, 8 looks like 1000, and so on. The straightforward approach just keeps dividing by 2 until hitting an odd number and checks whether that number is 1. The O(1) insight is the bit trick n & (n - 1): subtracting 1 flips every bit at and below the single set bit, so ANDing with the original always yields zero — and it yields zero for no other positive integer.

Approach 1 — Repeated Division

Strip factors of 2 one at a time; if you reach 1 you started with a power of two, and if you hit any other odd number you did not.

1. Return false if n ≤ 0.
2. While n is divisible by 2, divide n by 2.
3. Return whether n equals 1.

1def isPowerOfTwo(n: int) -> bool:
2    if n <= 0:
3        return False
4    while n % 2 == 0:
5        n //= 2  # strip one factor of 2 per iteration
6    return n == 1

Time: O(log n) — the loop runs at most log₂(n) iterations. Space: O(1) — no auxiliary storage.

Approach 2 — Bit Trick: n & (n − 1)

A power of two has exactly one set bit. Subtracting 1 turns that bit off and turns on every bit below it, so the AND of the original and the decremented value is always zero. This check is a single instruction.

1. Guard: return false if n ≤ 0 (the bit trick alone cannot reject zero — 0 & -1 == 0).
2. Return (n & (n - 1)) == 0.

1def isPowerOfTwo(n: int) -> bool:
2    return n > 0 and (n & (n - 1)) == 0

Time: O(1) — single bitwise operation regardless of n. Space: O(1) — no auxiliary storage.

Complexity Summary

Common Mistakes

• Omitting the n > 0 guard with the bit trick — 0 & (0 - 1) evaluates to 0 in two's complement, so the function incorrectly returns true for n = 0 without the guard.
• Using n >= 0 instead of n > 0 in the loop approach — n = 0 is even, so the while loop would divide 0 by 2 forever (0 // 2 == 0 in every language), producing an infinite loop.
• Float division in Python — writing n = n / 2 instead of n = n // 2 introduces floating-point drift for large inputs and breaks the remainder check.
• Confusing n & 1 with n & (n - 1) — n & 1 tests only the lowest bit (odd/even check); n & (n - 1) clears the lowest set bit entirely; they solve different problems.
• Assuming negative inputs are safe — powers of two are strictly positive; the explicit n > 0 guard is the correct and complete rejection of non-positive inputs, not a minor edge-case detail.

Related Problems

• number-of-1-bits — applies the same n & (n - 1) trick in a loop to count all set bits
• counting-bits — builds on single-number popcount to produce bit counts for every integer 0–n
• single-number — XOR bit manipulation to isolate the one unpaired element in an array
• reverse-bits — bit-by-bit manipulation across a fixed 32-bit integer
• bitwise-and-of-numbers-range — range AND exploits the same shared-prefix bit structure that defines powers of two