Pen in hand. Eyes barely open. LeetCode daily problem: "Power of Four."

My brain immediately went to the classic approach: "Just keep dividing by 4 until you can't anymore." You know, the algorithm equivalent of peeling an onion layer by layer until you either find the core or start crying.

But then I thought: "Wait, 4 is just $2^2$. So powers of 4 are powers of 2 with even exponents."

I started connecting the dots. Powers of 2 have that neat n & (n-1) trick. But how do I check if the exponent is even? That's when I went down the rabbit hole and discovered this cryptic 0x55555555 number through some desperate Googling.

Turns out, the past few days of power problems on LeetCode were actually a masterclass in "how to make your computer think you're a wizard." Let me break down what I figured out.

Power of Two: The "Oh Shit, That's Clever" Moment

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

When I first saw this, I was like "excuse me, what the ...?", but nowadays every CS student(or a programming nerd) knows this neat trick.

Here's the thing about powers of 2: they're the introverts of the binary world. They have exactly one bit set and that's it.

• $2^2 = 4$ = 100 (just that lonely 1 in position 2)
• $2^3 = 8$ = 1000 (one bit, chilling in position 3)
• $2^4 = 16$ = 10000 (you get the pattern)

Now, here's where it gets funky. The operation n & (n-1) is like a bit eraser that specifically targets the rightmost set bit.

Let's say $n = 8$:

• $n = 8$ = 1000
• $n-1 = 7$ = 0111 (notice how all bits to the right of the original 1 are now flipped)
• $n \& (n-1)$ = 1000 & 0111 = 0000

It's like the bits are playing hide and seek, and n & (n-1) always finds the last hiding spot and erases it.

For powers of 2, this operation nukes the only bit that exists, leaving you with 0. For anything else (like 6 = 110), some bits survive the massacre.

The beauty is that this works because of how binary subtraction works. When you subtract 1 from a power of 2, you're essentially borrowing from that single bit, which creates this perfect cancellation pattern.

Power of Three: When Bit Manipulation Gives Up and Goes Home

bool isPowerOfThree(int n) {
    return n > 0 && 1162261467 % n == 0;
}

Now, if Power of Two was a neat magic trick, Power of Three is like trying to perform magic while drunk. The bits don't line up nicely because 3 is odd, and odd numbers are the chaos agents of the binary world.

So what's this 1162261467 number?

I couldn't use the same bit tricks, so I thought: "What if I find the biggest power of 3 that fits in a 32-bit integer?" If any number is a power of 3, it should divide this ultimate power of 3, right?

So I fired up a calculator and kept multiplying: $3^1 = 3$, $3^2 = 9$, $3^3 = 27$... and kept going until $3^{19} = 1162261467$. One more multiplication and boom 💣 integer overflow. That's my magic number.

The logic is hilariously simple: if $n$ is a power of 3, then it must divide the ultimate power of 3. It's like saying "if you're really part of this family, then the family patriarch should be divisible by you."

Mathematically: if $n = 3^k$ for some integer $k$, then $3^{19} = 3^k \times 3^{19-k}$, which means $3^{19} \bmod 3^k = 0$.

The alternative is the "peel the onion" approach:

bool isPowerOfThree(int n) {
    if (n <= 0) return false;
    while (n % 3 == 0) n /= 3;
    return n == 1;
}

Keep dividing by 3 until you either hit 1 (success!) or hit something that's not divisible by 3 (imposter detected).

Power of Four: Decoding the Alien Message

And now, the pièce de résistance that started this whole journey:

bool isPowerOfFour(int n) {
    if (n <= 0) return false;
    return !(n & (n - 1)) && (n & 0x55555555) != 0;
}

This looks like someone encrypted their password and then used it as code. Let me decode this alien message.

Step 1: !(n & (n - 1)) - "Are you a power of 2?" (We already know this trick)

Step 2: (n & 0x55555555) != 0 - "But are you a special power of 2?"

Here's the plot twist: any power of 4 can be written as $(2^2)^k = 2^{2k}$. So powers of 4 are just powers of 2 where the exponent is even.

In binary terms, this means the single bit must be at an even position (counting from 0):

• $4^0 = 1$ = 1 (position 0) ✓
• $4^1 = 4$ = 100 (position 2) ✓
• $4^2 = 16$ = 10000 (position 4) ✓

But imposters like $2^1 = 2$ = 10 (position 1) and $2^3 = 8$ = 1000 (position 3) have their bits at odd positions.

Now, 0x55555555 in binary is: 01010101010101010101010101010101

It's a mask with 1s at all even positions! So n & 0x55555555 will be non-zero only if $n$ has a bit at an even position.

It's like having a bouncer at a club who only lets in people whose IDs end in even numbers. The mask is the bouncer, and even positions are the VIP list.

The math checks out: if $n = 2^{2k}$ (a power of 4), then $n$ has a bit set at position $2k$ (even), so n & 0x55555555 ≠ 0. If $n = 2^{2k+1}$ (power of 2 but not 4), then the bit is at position $2k+1$ (odd), so n & 0x55555555 = 0.

brilliant!!

And that's the story of how I went from dividing numbers like a caveman to speaking fluent binary in the morning. Sometimes the most elegant solutions are hiding behind the most cryptic-looking code.

Now excuse me while I go apply this 0x55555555 wisdom to every bit manipulation problem I can find. The aliens who invented this notation are probably laughing at us somewhere.

If you enjoyed this deep dive into algorithmic thinking, you might also like my posts on building an LRU cache from scratch or understanding bloom filters - both involve similar "aha!" moments when elegant solutions click into place.

Links:

• LeetCode Power of Two
• LeetCode Power of Three
• LeetCode Power of Four
• Bit Manipulation Patterns
• My own thing: Bit Manipulation Patterns