342. Power of Four

Given an integer (signed 32 bits), write a function to check whether it is a power of 4.

Example 1:

Input: 16
Output: true

Example 2:

Input: 5
Output: false

Follow up: Could you solve it without loops/recursion?

// Naive
bool isPowerOfFour(int num) { // time: O(logn); space: O(1)
    if (num == 0) return false;
    if (num == 1) return true;
    int n = num;
    while (n > 1) {
        if (n % 4 != 0) return false;
        n /= 4;
    }
    return n == 1;
}

4^0 = 1 4^1 = 4 (100) 4^2 = 16(1000) 4^3 = 64(10000) ... 可以觀察到4的power在2進位表示時都只有一個digit 1，其他都是0。 bit manipulation中的n & (n - 1)操作會得到一個移除最後一個digit 1的結果，因為4的power只有一個1，所以操作完之後應該要得到0。 0x55555555是為了在32-bit的integer中取到位於奇數位置的digit 1，0x55在二進位表示為01010101，位於奇數位置的1才能組成4的power。

// Bit Manipulation
bool isPowerOfFour(int num) { // time: O(1); space: O(1)
    // num & (num - 1): remove the last significant digit
    // if a number is power of 4, it only has one digit-1
    // 0x55555555 is to select out digit-1s in odd positions in binary representation
    return num > 0 && (num & (num - 1)) == 0 && (num & 0x55555555) != 0;
}