Power of Two

easy math bit manipulation recursion

Problem

Given an integer n, return true if and only if it is a power of two.

Inputn = 16

Outputtrue

A power of two has exactly one set bit. Subtracting 1 flips that bit and all bits below it, so n & (n − 1) clears it — and the result is 0 only when there was exactly one bit. Guard against n ≤ 0.

def is_power_of_two(n):
    return n > 0 and (n & (n - 1)) == 0

function isPowerOfTwo(n) {
  return n > 0 && (n & (n - 1)) === 0;
}

class Solution {
    public boolean isPowerOfTwo(int n) {
        return n > 0 && (n & (n - 1)) == 0;
    }
}

bool isPowerOfTwo(int n) {
    return n > 0 && (n & (n - 1)) == 0;
}

Explanation

A number is a power of two exactly when its binary form has exactly one set bit — like 1, 10, 100, and so on. So the whole problem boils down to checking "does n have a single 1 bit?".

The neat trick is n & (n - 1). Subtracting 1 from a power of two flips its only set bit to 0 and turns every bit below it into 1. ANDing that with the original n wipes out the result entirely, giving 0.

If n had more than one set bit, subtracting 1 would only affect the lowest one, and the higher bits would survive the AND — so the result would not be zero.

We also need n > 0, because zero and negatives are not powers of two. That is why the check is n > 0 && (n & (n - 1)) == 0.

Example: n = 16 = 10000, so n - 1 = 15 = 01111, and 10000 & 01111 = 0 — true. But n = 6 = 110 gives 6 & 5 = 100, which is non-zero — false.

Time: O(1) Space: O(1)