Check If a Number is Power of Two – Tech Interview Dot Org

What code will you write to check if a number is power of two or not?

💡Strategies for Solving This Problem

Bit Manipulation Gold

This is a 5-minute interview question that separates people who know bit tricks from those who don't. I learned this the hard way at Facebook.

The Naive Approach

Keep dividing by 2 until you hit 1 or an odd number. Works but it's O(log n) and shows you don't know the bit trick.

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

The Bit Trick

Powers of 2 in binary have exactly one bit set:

1 = 0001
2 = 0010
4 = 0100
8 = 1000

Key insight: n & (n-1) clears the lowest set bit. For power of 2, this gives 0.

Example:

8 = 1000
7 = 0111
8 & 7 = 0000 ✓

But for non-power-of-2:

6 = 0110
5 = 0101
6 & 5 = 0100 ✗ (not zero)

One-Liner Solution

return n > 0 && (n & (n - 1)) === 0;

That's it. O(1) time, O(1) space, and shows you know bit manipulation.

Why This Matters

My Facebook interviewer asked this as a warm-up. I gave the division approach. He said "Can you do it in O(1)?" I couldn't figure it out in time. Didn't get the offer.

Learn the bit tricks. They come up more than you'd think.

✅Solution

Solution: Bit Manipulation

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

Why It Works: Bit-Level Analysis

Powers of 2:

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

Each has exactly ONE bit set.

What n-1 does:

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

8 & 7:  00000000  (no overlap = 0)

Non-powers of 2:

6:    00000110  (two bits set)
5:    00000101

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

Alternative Bit Tricks

Method 2: Count set bits

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;
}

This works but is O(log n) instead of O(1). The first solution is better.

Common Edge Cases

n = 0: Not a power of 2 (no power gives 0)
n < 0: Negative numbers can't be powers of 2
n = 1: Yes! 2^0 = 1
Very large n: Works as long as it fits in integer

Follow-Up: What if n can be 3^k?

My interviewer asked: "What if we want to check if it's a power of 3?"

The bit trick doesn't work. For powers of 3, you have to use division:

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;
}

The second version only works if you know the max power upfront.

Complexity

Time: O(1) - Single bitwise AND operation
Space: O(1) - No extra memory

Compare to division approach: O(log n) time.

Pro tip: When you see "power of 2" in an interview, think bits. There's almost always a clever bit trick.