判断是否是4的幂

  1. 解题思路:
    1. 先判断是否是2的幂,参考之前的代码
    2. 然后两种解法:
      1. 如果n是4的次方的数,其二进制位表示中有且仅有1个1,这是由是否是2的幂得到的,其次1只出现在偶数位置,比如1的二进制就是1,1出现在第0位,4的二进制是100,1出现在第二位等等,因此可以构造一个32位数,1010101010…进行与运算,其所有偶数位置都为0,奇数位置都为1,这样进行与运算的时候,如果n是4的幂,其有一个偶数位置为1,奇数位置为0,结果==0。
      2. 4^x=(3+1)^x=1^x=1(mod)3,除以 3的余数一定为 ,如果n是2的幂,不是4的幂,其可以表示成4^x*2,其与3的模为2。
        class Solution {
        public:
            bool isPowerOfFour(int n) {
                return n > 0 && (n & (n - 1)) == 0 && (n & 0xaaaaaaaa) == 0;
            }
        };
        
        class Solution {
        public:
            bool isPowerOfFour(int n) {
                return n > 0 && (n & (n - 1)) == 0 && n % 3 == 1;
            }
        };
        
        作者:LeetCode-Solution
        链接:https://leetcode-cn.com/problems/power-of-four/solution/4de-mi-by-leetcode-solution-b3ya/
        来源:力扣(LeetCode)
        

发表评论

邮箱地址不会被公开。 必填项已用*标注