Check If a Number Is a Power of Two: Bit Manipulation and Variations

Check If a Number Is a Power of Two: Bit Manipulation, Math, and Variations

“Is this number a power of two?” is one of the simplest bit-manipulation interview questions. It comes up at FAANG, AI labs, fintechs, and most coding screens that include any low-level questions. The expected one-liner uses the n & (n - 1) == 0 trick. Interviewers also ask follow-ups: power of three, power of four, count set bits — all using related bit-manipulation patterns. This guide covers the standard answers, why each works, and the broader bit-trick toolkit interviewers expect.

Problem Statement

Given an integer n, return True if n is a power of two, otherwise False.

Examples:

• n = 1 → True (2⁰)
• n = 16 → True (2⁴)
• n = 218 → False
• n = 0 → False
• n = -16 → False (powers of two are positive by convention)

Approach 1: Bit Trick (Standard Answer)

A power of two has exactly one bit set in its binary representation: 1 = 0001, 2 = 0010, 4 = 0100, 8 = 1000, etc. Subtracting 1 from such a number flips that bit and sets all bits below it: 4 = 0100, 4-1 = 0011. The bitwise AND of these is zero: 0100 & 0011 = 0000.

For non-powers of two, the highest bit doesn’t flip alone, so the AND has at least one set bit.

def is_power_of_two(n: int) -> bool:
    """O(1) time and space."""
    return n > 0 and (n & (n - 1)) == 0


# Tests
print(is_power_of_two(1))     # True
print(is_power_of_two(16))    # True
print(is_power_of_two(218))   # False
print(is_power_of_two(0))     # False
print(is_power_of_two(-16))   # False

Why n > 0? The bit trick alone passes 0 as a power of two (0 & -1 == 0) and may pass negative numbers depending on the language’s two’s-complement representation. The explicit positivity check guards against both.

Complexity: O(1) time, O(1) space.

Approach 2: Iterative Division

Repeatedly divide by 2 until the number is 1 (success) or odd (failure). Conceptually clean; slower than the bit trick.

def is_power_of_two_iter(n: int) -> bool:
    """O(log n) time."""
    if n <= 0:
        return False
    while n % 2 == 0:
        n //= 2
    return n == 1

Complexity: O(log n) time, O(1) space. Acceptable as an alternative answer; interviewers prefer the bit trick.

Approach 3: Logarithm

Take the log base 2; check whether the result is an integer. Floating-point pitfalls make this fragile.

import math

def is_power_of_two_log(n: int) -> bool:
    """O(1) time but floating-point fragile."""
    if n <= 0:
        return False
    log = math.log2(n)
    return log == int(log)

Generally avoid this in interviews. Log-based approaches have rounding issues for large numbers (e.g., math.log2(2**53) != 53 exactly in some IEEE-754 corner cases). Mention as an option, then move on.

The Bit-Trick Toolkit

Several related tricks share the n & (n - 1) pattern. Worth knowing as a coherent set:

Clear the lowest set bit

n & (n - 1): if n = ...100100, then n - 1 = ...100011, so n & (n - 1) = ...100000 — the lowest 1 bit cleared. Used for power-of-two check (zero result) and for counting set bits (Brian Kernighan’s algorithm).

Isolate the lowest set bit

n & -n: extracts only the lowest 1 bit. Used in Fenwick trees / Binary Indexed Trees.

Set the lowest unset bit

n | (n + 1): opposite of clear-lowest-set-bit; sets the lowest 0 bit.

Count set bits (Brian Kernighan’s)

def count_set_bits(n: int) -> int:
    """O(k) where k = number of set bits."""
    count = 0
    while n:
        n &= n - 1
        count += 1
    return count

Check if exactly one bit is set

Same as power-of-two check: n > 0 and (n & (n - 1)) == 0.

Common Variations

Power of three

(LeetCode #326) No clean bit trick. Standard approach: divide by 3 until 1, or check whether n divides 3^19 (the largest power of 3 fitting in a 32-bit int).

def is_power_of_three(n: int) -> bool:
    """O(1) time using max-power-of-3 divisibility check."""
    return n > 0 and 1162261467 % n == 0
    # 1162261467 = 3^19 (largest power of 3 in 32-bit int)

Power of four

(LeetCode #342) Combine power-of-two check with mask check: n & 0x55555555 selects bits at even positions (0, 2, 4, …). Powers of four have their single bit at an even position.

def is_power_of_four(n: int) -> bool:
    """Power of two AND single bit at an even position."""
    return n > 0 and (n & (n - 1)) == 0 and (n & 0x55555555) != 0

Hamming weight

(LeetCode #191) Count the number of 1 bits in a binary representation. Brian Kernighan’s algorithm above; or use built-in bin(n).count("1") in Python or __builtin_popcount(n) in C++.

Single number / find the missing element

(LeetCode #136) XOR all elements; pairs cancel, leaving the unique element. Bit manipulation again — different trick (XOR self-inverse property), same family.

Common Mistakes

• Forgetting the positive check. Without n > 0, the function returns True for 0 and may return True for negative powers in two’s-complement. Always guard.
• Using floating-point logarithm. math.log2(8) == 3 works but math.log2(2**53) may return 52.99999999... on some platforms due to rounding. Avoid.
• Returning True for n = 0. Zero is not a power of two; the smallest positive power is 2⁰ = 1.
• Confusing power of two with even number. 6 is even but not a power of two. The bit trick distinguishes them correctly; iterative division by 2 (without the “n == 1” check at the end) does not.
• Misunderstanding negative numbers. In Python, integers are arbitrary precision, so -1 & -2 is -2 due to two’s-complement representation. The bit trick can give surprising results for negative inputs; the positive check sidesteps this.

Frequently Asked Questions

See also: Two Sum: Find a Pair in an Array • Missing or Duplicate Number in an Array • XOR Using NAND Gates

// Don't do this
function isPowerOfTwo(n) {
    if (n <= 0) return false;
    while (n % 2 === 0) {
        n = n / 2;
    }
    return n === 1;
}

function isPowerOfTwo(n) {
    // Power of 2 has exactly one bit set
    // n & (n-1) clears the lowest bit
    // For power of 2, result is 0
    return n > 0 && (n & (n - 1)) === 0;
}

// Tests
console.log(isPowerOfTwo(1));    // true (2^0)
console.log(isPowerOfTwo(16));   // true (2^4)
console.log(isPowerOfTwo(3));    // false
console.log(isPowerOfTwo(0));    // false
console.log(isPowerOfTwo(-16));  // false

// Edge cases
console.log(isPowerOfTwo(1024)); // true (2^10)
console.log(isPowerOfTwo(1000)); // false

1:    00000001
2:    00000010
4:    00000100
8:    00001000
16:   00010000

8:    00001000
7:    00000111  (all bits below the set bit flip)

8 & 7:  00000000  (no overlap = 0)

6:    00000110  (two bits set)
5:    00000101

6 & 5:  00000100  (still has bits set ≠ 0)

function isPowerOfTwoCountBits(n) {
    if (n <= 0) return false;

    let count = 0;
    while (n > 0) {
        count += n & 1;  // Add 1 if lowest bit is set
        n >>= 1;         // Shift right
    }

    return count === 1;
}

function isPowerOfThree(n) {
    if (n <= 0) return false;

    while (n % 3 === 0) {
        n = n / 3;
    }

    return n === 1;
}

// Or one-liner (assuming 32-bit int)
function isPowerOfThreeTrick(n) {
    // 3^19 = 1162261467 is largest power of 3 in 32-bit int
    return n > 0 && 1162261467 % n === 0;
}