Power of Four — Editorial

Opening the reading…

Intuitionwhy one bit position identifies every power of four

The powers of four are 1, 4, 16, 64, and so on. In binary, each multiplication by four shifts the only set bit left by two positions: 1 is 1, 4 is 100, 16 is 10000, and 64 is 1000000. Therefore, the answer is determined by two facts: there must be exactly one set bit, and its zero-based position must be even.

The expression n & (n - 1) removes the lowest set bit. It becomes zero exactly when n has one set bit, which recognizes every positive power of two. To separate powers of four from powers of two such as 2, 8, and 32, inspect the bit positions with odd indices. The mask 0xaaaaaaaa has ones at positions 1, 3, 5, and so on, so a valid power of four must have no overlap with it.

Approach

Reject n <= 0, because powers of four are positive and the bit tests alone could otherwise treat an invalid value incorrectly.

Check (n & (n - 1)) == 0, because a power of four must contain exactly one set bit; this also removes values with several set bits such as 5.

Check (n & 0xaaaaaaaa) == 0, because the mask covers every odd bit position and a power of four places its only set bit at an even position.

Return true only when all three conditions hold, so values such as 16 pass while 2 and 5 fail for different reasons.

Complexityconstant work on a fixed-width integer

MEASURE	BOUND	WHY
Time	O(1)	The solution performs a fixed number of integer comparisons and bitwise operations. A 32-bit integer has a fixed representation, so no loop scans an input-dependent number of bits.
Space	O(1)	Only the input and a fixed number of temporary values are used. The boolean result is required output and is excluded from the extra-space bound; the bound stays constant for every allowed input shape.

Annotated solutionC++ · bit checks · the three conditions mirror the definition

CPPChecks positivity, a single set bit, and an even bit position.

#include <cstdint>

using namespace std;

class Solution {
public:
    bool isPowerOfFour(int n) {
        return n > 0 &&
               (n & (n - 1)) == 0 &&
               (n & 0xaaaaaaaa) == 0;
    }
};

The order of the conditions makes the reasoning easy to audit. Positivity removes zero and negatives before they reach the bit logic. The n & (n - 1) test proves that exactly one bit is set. Once that is known, the mask test only needs to decide whether that one bit is in an odd position; no loop or conversion to a string is necessary.

The divisibility alternativea different test for the same even exponent

You can replace the position mask with modular arithmetic. First confirm that n is a positive power of two. Powers of two alternate modulo 3: 2 has remainder 2, 4 has remainder 1, 8 has remainder 2, and 16 has remainder 1. Thus a positive power of two is a power of four exactly when n % 3 equals 1, or equivalently when n - 1 is divisible by 3.

CPPUses modulo 3 to distinguish even and odd powers of two.

#include <cstdint>

using namespace std;

class Solution {
public:
    bool isPowerOfFour(int n) {
        return n > 0 &&
               (n & (n - 1)) == 0 &&
               n % 3 == 1;
    }
};

This is not an asymptotic optimization: both versions use constant time and constant extra space. The mask version exposes the exact bit-position rule and avoids arithmetic reasoning. The modulo version is shorter conceptually once you know the alternating remainders, but the mask is often easier to generalize when a problem asks about particular bit positions.