power-of-four

Power of Four – LeetCode 342

Problem

Description

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

Answer

Original

Code

class Solution {
public:
    bool isPowerOfFour(int num) {
        if(!num) return false;
        unsigned n = (unsigned)num;
        unsigned tmp = ((n - 1) ^ n) + 1;
        return !(tmp & 0x55555555) && (tmp >> 1 == n);
    }
};

思路

依旧是位操作，先判断是否为2的模，再判断4的模。时间复杂度$O(1)$，空间复杂度$O(1)$。
耗时$4$ ms，排名$76.73\%$

Better

思路

这个写法更简洁。
耗时$4$ ms，排名$76.73\%$

Code

class Solution {
public:
    bool isPowerOfFour(int num) {
        return num > 0 && !(num & (num - 1)) && (num & 0x55555555) == num;
    }
};