leetcode题解-324-4的幂

发表于 | 更新于 | 分类于

题目

非位运算解：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    bool isPowerOfFour(int num) {
        
        if (num == 0) return false;

        int mod;

        while (num != 1)
        {
            mod = num % 4;
            num /= 4;
            
            if (mod != 0)
            {
                return false;
            }
        }

        return true;
    }
};

位运算：

1
2
3
4
5
6
class Solution {
public:
    bool isPowerOfFour(int num) {
        return num > 0 && !(num&(num-1)) && !(num & 0xAAAAAAAA);
    }
};

考虑：

  • num > 0时，才会是一个数的幂。负数和0不会是一个正整数的幂。
  • !(num&(num-1))时，用来判断num是不是2的幂，
    • 因为一个数是2的幂的话，则它2进制的第一位必然是1，与num-1与运算后，结果必然为0
  • !(num & 0xAAAAAAAA), 用来判断num是不是4的幂，
    • 因为一个数是4的幂的话，则它2进制必然第一位是1且第一位是奇数位，0xA=1010，则4的幂与其求与运算后，则为0，求反得1

总结

位运算小技巧：

  • !(n&(n-1))，用于判断n是不是2的幂
  • !(num&(num-1)) && !(num & 0xAAAAAAAA), 用于判断n是不是4的幂
  • 对于n的幂，可以先枚举一定的例子，然后对枚举结果进行归纳找到规律。

Reference

https://leetcode-cn.com/problems/power-of-four/solution/e-you-shi-yi-dao-zhuang-bi-jie-fa-de-suan-fa-ti-2/

https://www.geeksforgeeks.org/program-to-find-whether-a-no-is-power-of-two/

https://www.geeksforgeeks.org/find-whether-a-given-number-is-a-power-of-4-or-not/