4的幂

Trace

5.31 每日一题

传送门：https://leetcode-cn.com/problems/power-of-four/

Problem

暴力

class Solution {
public:
    bool isPowerOfFour(int n) {
        for(int i=0; i<=16; i++){
            if(pow(4, i)==n) return true;
        }
        return false;
    }
};

二进制中1的位置

如果一个数是4的幂，那么它也一定是2的幂，判断一个数是否为2的幂，可以用x&(x-1)来判断

如果一个数为2的幂，则其二进制表示含且只含1；4的幂次：1，100，10000，1000000…，其二进制表示只含有一个1，且1所在的位置在奇数位（从低位往高位看，且最低位为第1位）

最后判断唯一的一个1在奇数位还是偶数位，可以用x&0x55555555来判断（0x5=0x0101可以判断奇数位上的1）

class Solution {
public:
    bool isPowerOfFour(int n) {
        if(n<=0) return false;
        if(n&(n-1)) return false;
        if(n&0x55555555) return true;
        return false;
    }
};

取模

首先判断n是不是2的幂

如果n是4的幂，那么它模3结果为1

$$4^n\equiv(3+1)^n\equiv1^n\equiv1\pmod n$$

如果n是2的幂确不是4的幂，那么n可以表示为2*4的幂，其模3结果为2

class Solution {
public:
    bool isPowerOfFour(int n) {
        if(n<=0) return false;
        if(n&(n-1)) return false;
        if(n%3==1) return true;
        return false;
    }
};