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

Source: https://www.techinterview.org/post/3233459629/check-if-a-number-is-power-of-two/
Updated: 2026-04-27 · techinterview.org

## 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

### What's the expected interview answer?

  The bit trick: `n > 0 and (n & (n - 1)) == 0`. Walk through why it works (powers of two have exactly one bit set; subtracting 1 flips that bit and sets all lower bits; AND of the two is zero). Mention iterative division as a fallback. Strong candidates also state the variations (power of three, power of four) and demonstrate the related bit tricks.

### Why is the bit-trick approach considered better than iterative division?

  Both are correct; the bit trick is O(1) time vs O(log n) for iteration. The bit trick is also a recognized idiom — it signals to interviewers that you know bit manipulation. For numbers that fit in a register, the bit trick maps to one or two machine instructions; iterative division involves multiple comparisons and divisions. The performance difference is rarely noticeable, but the idiom is widely expected.

### How does this generalize to "is power of k"?

  For k = 2, the bit trick works. For k = 3, no clean bit trick exists; use divisibility into the largest power of 3 in your int range, or iterative division. For k = 4, combine power-of-two check with a mask. In general, no universal trick works for arbitrary k; iterative division is always available.

### What if I need to find the largest power of two ≤ n?

  Different problem. Approaches: bit_length() in Python (`1 << (n.bit_length() - 1)` for positive n) or `__builtin_clz` in C++. Or repeatedly clear the lowest set bit with the bit trick, but in the opposite direction: keep only the highest bit. The "clear lowest" trick gives you the next-smaller power of two by subtraction.

### Why do interviewers ask about powers of two?

  Powers of two are foundational to computer science: memory page sizes, hash table capacities, binary tree levels, etc. The bit-manipulation idiom is well-known and signals familiarity with low-level computing. The question itself takes 30 seconds; interviewers use the remaining time for follow-ups (count set bits, find missing number, etc.) that test the broader bit-trick toolkit.

See also: [Two Sum: Find a Pair in an Array](/post/3233459633/sum-up-a-pair-in-array/) • [Missing or Duplicate Number in an Array](/post/3233459624/missing-or-duplicate-number-in-an-array/) • [XOR Using NAND Gates](/post/3233459573/xor-using-nand-gates/)