Bit Manipulation LeetCode 342 Power of Four

342. Power of Four

Observations

• a⁴ can only be positive
• 4⁰, 4¹, 4², 4³… 4^n are valid numbers
• the binary of those 4⁰, 4¹, 4², 4³… 4^n are 1 (0b1), 4 (0b100), 16 (0b10000), 64 (0b1000000),…
• we can assume valid results’ binary number will 1) only contain one 1, 2) the number of trailing zeros will be an even number.
• We can use \__builtin_popcount(num) in C++ to get the number of 1s.
• We can use \__builtin_ctz(num) to get the bit position as the ctz is short for count trailing zeros.
• Proof of the correctness of the assumptions can be found at the end of this article.

Code

class Solution {
public:
    bool isPowerOfFour(int num) {
        return (num > 0 && 
                __builtin_popcount(num) == 1 && 
                __builtin_ctz(num) % 2 == 0);
    }
};

proof

It is easy to **prove** the correctness of the answer by induction
we can easily prove that
- 4⁰ = 1 is correct
- 4¹ = 4 is correct
- 4² = 16 is correct
- 4³
- 4⁴
- …
- 4^n
- 4^(n+1) = (4^n)*4 = 4^(n+1)

We know for binary numbers, shift left by 1 bit is multple by 2, shift to left two bits is multiple by 4.

Done the proof.