Is power of two?

You are in a phone screen at Blizzard and the interviewer asks: "Given a positive integer, determine if it's a power of two, but do it in constant time and space." This problem, also known as Power of Two on other platforms, sounds trivial until you realize that loops and division are off the table. The key is a single bitwise trick that every systems programmer should know.

TL;DR

Use num & (num - 1) == 0. Powers of two have exactly one bit set in binary. Subtracting 1 flips that bit and sets all lower bits. The AND of these two values is zero only for powers of two. This runs in O(1) time and O(1) space.

Why This Problem Matters

Bit manipulation problems show up regularly in interviews at companies that care about low-level efficiency. The num & (num - 1) pattern is one of the most useful bitwise idioms. It also appears in problems like counting set bits (Brian Kernighan's algorithm), and understanding it gives you a foundation for harder bit manipulation challenges.

Understanding the Problem

We need to write a method that:

• Takes a positive integer as input
• Returns true if the number is a power of 2, false otherwise
• Runs in O(1) time and O(1) space

isPowerOfTwo(2)   -> true
isPowerOfTwo(5)   -> false

The Binary Pattern

The trick starts with a simple observation: every power of two has exactly one bit set in its binary representation.

Notice the pattern. Each power of two is a single 1 followed by zeros. No other positive integers share this property. The number 5, for example, is 101 in binary, with two bits set. The number 6 is 110, also two bits. Only powers of two have that lone 1-bit.

Solution Approach

The brute-force way is to keep dividing by 2 and check whether you ever get a remainder. That works, but it runs in O(log n) time and the problem explicitly asks for constant complexity.

A better approach uses bitwise AND. When you subtract 1 from a power of two, something interesting happens in binary. Let's trace through with num = 8:

The number 8 is 1000 in binary. Subtracting 1 gives 7, which is 0111. Every bit flips. When you AND them together, no bit positions overlap, so the result is 0000. That means the number is a power of two.

Now let's see what happens with num = 5, which is not a power of two:

The number 5 is 101 in binary. Subtracting 1 gives 4, which is 100. The AND of 101 and 100 is 100, which is 4. Since the result is not zero, we know 5 is not a power of two.

This works because subtracting 1 from any number flips the lowest set bit and all the bits below it. For a power of two, the lowest set bit is the only set bit, so the entire number becomes zero after the AND.

Implementation

Prefer a different language? Jump to solutions in other languages.

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

That's the entire solution. One line of logic.

Let's break down what happens:

1. num - 1: Flips the lowest set bit and all bits below it
2. num & (num - 1): Clears the lowest set bit of num
3. == 0: If the result is zero, num had exactly one bit set, meaning it is a power of two

The parentheses around num & (num - 1) matter in Java (and most languages). The == operator has higher precedence than &, so without parentheses, the expression would be parsed as num & ((num - 1) == 0), which is not what we want.

Complexity Analysis

Time: O(1). The bitwise AND operation and subtraction each take constant time, regardless of how large the number is. There are no loops, no recursion, and no function calls that scale with input size.

Space: O(1). We use no extra data structures. The computation happens entirely in registers.

Why Not Use Division?

The division approach looks like this:

// Works, but O(log n) time
while (num > 1) {
  if (num % 2 != 0) return false;
  num /= 2;
}
return true;

This divides by 2 repeatedly, checking for remainders. It runs in O(log n) time because you halve the number at each step. The bitwise approach is strictly better: same correctness, constant time.

Common Pitfalls

1. Missing parentheses around the AND expression: In Java, C++, and many other languages, == binds more tightly than &. Writing num & (num - 1) == 0 without the outer parentheses evaluates as num & 0, which is always 0 and always returns true.

2. Not handling zero: 0 & (-1) is 0, which would incorrectly return true. This problem guarantees positive inputs (greater than 0), but in a general implementation you would add a check: num > 0 && (num & (num - 1)) == 0.

3. Confusing & with &&: The single & is a bitwise AND. The double && is a logical AND. They are different operations. You need the bitwise version here.

Interview Tips

When presenting this solution:

• Start by writing out the binary representation of a few powers of two: 1 = 1, 2 = 10, 4 = 100, 8 = 1000. Point out the single-bit pattern.
• Show the subtraction trick on the whiteboard: 1000 - 1 = 0111, then AND them together.
• Mention Brian Kernighan's algorithm for counting set bits, which uses the same num & (num - 1) trick in a loop.
• If asked about edge cases, mention zero and negative numbers, even though this problem rules them out.

Key Takeaways

• Powers of two have exactly one bit set in binary. This is the foundational insight for the solution.
• The expression num & (num - 1) clears the lowest set bit. For powers of two, clearing the only set bit gives zero.
• Bitwise operations run in O(1) time and O(1) space, making them ideal when the problem constrains complexity.
• Always wrap bitwise expressions in parentheses before comparing with ==. Operator precedence can silently produce wrong results.
• This same num & (num - 1) pattern powers Brian Kernighan's bit-counting algorithm and appears in many other bit manipulation problems.

Practice and Related Problems

Once you're comfortable with this power-of-two check, try these progressions:

• Count the number of set bits in an integer (Hamming weight)
• Reverse the bits of a 32-bit integer
• Find the single number in an array where every other number appears twice (XOR trick)

This problem and hundreds of others are available on Firecode, where consistent daily practice helps you build the pattern recognition that top tech companies look for. Whether you're warming up for phone screens or preparing for on-site interviews, starting with fundamentals like this sets you up well.

Solutions in Other Languages

Python

class Solution:
    def is_power_of_two(self, num: int) -> bool:
        return (num & (num - 1)) == 0

JavaScript

class Solution {
  isPowerOfTwo(num) {
    return (num & (num - 1)) === 0;
  }
}

TypeScript

class Solution {
  isPowerOfTwo(num: number): boolean {
    return (num & (num - 1)) === 0;
  }
}

C++

#include <iostream>

class Solution {
public:
  bool isPowerOfTwo(int num) {
    return (num & (num - 1)) == 0;
  }
};

Go

package solution

func (s *Solution) IsPowerOfTwo(num int) bool {
    return (num & (num - 1)) == 0
}

Scala

class Solution {
  def isPowerOfTwo(num: Int): Boolean = {
    (num & (num - 1)) == 0
  }
}

Kotlin

class Solution {
    fun isPowerOfTwo(num: Int): Boolean {
        return (num and (num - 1)) == 0
    }
}

Swift

import Foundation

class Solution {
    func isPowerOfTwo(_ num: Int) -> Bool {
        return (num & (num - 1)) == 0
    }
}

Rust

impl Solution {
    pub fn is_power_of_two(&self, num: i32) -> bool {
        (num & (num - 1)) == 0
    }
}

C#

public class Solution {
    public bool isPowerOfTwo(int num) {
        return (num & (num - 1)) == 0;
    }
}

Dart

class Solution {
  bool isPowerOfTwo(int num) {
    return (num & (num - 1)) == 0;
  }
}

PHP

class Solution {
    public function isPowerOfTwo(int $num): bool {
        return ($num & ($num - 1)) == 0;
    }
}

Ruby

class Solution
  def is_power_of_two(num)
    (num & (num - 1)) == 0
  end
end