The O(n) Club: Power of Two — Bitwise Magic and the Ancient Single-Bit Prophecy

The O(n) Club: Power of Two — Bitwise Magic and the Ancient Single-Bit Prophecy

⚡ TL;DR

Don’t know if your number is a power of two? Skip the drama—just use a bit trick. No endless division, no floating-point breakdowns, just pure geek glory:

// Java one-liner. Blink and you’ll miss it.
boolean isPowerOfTwo(int n) {
  return n > 0 && (n & (n - 1)) == 0;
}

🧠 How Devs Usually Mess This Up

Look, we’ve all been tempted to overcomplicate. Common slip-ups:

🔍 What’s Actually Going On

Here’s the secret ingredient: powers of two have exactly one ‘1’ in their binary recipe, followed by zeroes like silent party guests.

🛠️ PseudoCode

• Step 1: If n <= 0, return false. (No negative energy allowed.)
• Step 2: If (n & (n-1)) == 0, return true. (Our “single shining star” bit test.)
• Step 3: Otherwise? Nope, not a power of two. Go home, n.

💻 The Code

public boolean isPowerOfTwo(int n) {
    // Negative numbers and zero have no place at this party.
    if (n <= 0) return false;
    // The real magic—bitwise single-bit test
    return (n & (n - 1)) == 0;
}

⚠️ Pitfalls, Traps & Runtime Smacks

• Zero & Negatives: Sorry, Zeno—powers of two are strictly positive privileges.
• Int Wrapping: Java’s signed 32-bits means really big numbers get weird. Don’t play brinkmanship with Integer.MAX_VALUE, okay?
• Division Nostalgia: Safe, but O(log n) is so 1999. Come to the light side, O(1).
• Floating Point Fever: Don’t even. Math.log and rounding errors are a trap.
• Complexity: Bitwise AND is constant time. Fast as your next coffee hit.

🧠 Interviewer Brain-Tattoo

“If you want to power up your code, check your bits—and make sure there’s just one star shining!”