[数据结构与算法]【力扣】2的幂，3的幂，4的幂

一，循环法，通解—O(logN)

虽然这些题目中的进阶部分都说不用循环或者递归，但是对于3的幂这题来说，除非记得3的19次方是int型里最大的3的幂（然后判断n能不能被其整除），否则3的幂这题就只能用循环了！！！

首先，是n不能为小于等于0的数，然后对n进行整除，比如n /= 2；或 n /= 3; while循环的退出条件是n % 2 != 0或n % 3 != 0.

以3的幂举例，n不是3的幂的话，它既满足 n % 3 != 0，又满足 n != 1.

（注意1是所有正整数的幂）

（1）2的幂

class Solution {
public:
    bool isPowerOfTwo(int n) {
        // 先判断是否为正整数
        if(n <= 0) return false;
        while(n % 2 == 0){
            n /= 2;
        }
        if(n == 1) return true;
        else return false;
    }
};

简洁点的：

bool isPowerOfTwo(int n) {
    if(n <= 0) return false;
    while(n % 2 == 0){
        n /= 2;
    }
    return n == 1;
}

（2）3的幂

bool isPowerOfThree(int n) {
    if(n <= 0) return false;
    while(n % 3 == 0){
        n /= 3;
    }
    return n == 1;
}

这题还可以记住一个结论：在题目给定的 323232 位有符号整数的范围内，最大的 333 的幂为 3¹⁹=11622614673
我们只需要判断 n 是否是 3¹⁹的约数。这样时间复杂度就从O(logN)变成O(1)

不用循环的方法（记住19次方这个结论）：

bool isPowerOfThree(int n) {
    int m = pow(3, 19);
    return n > 0 && m % n == 0;
}

（3）4的幂

bool isPowerOfFour(int n) {
    if(n <= 0) return false;
    while(n % 4 == 0){
        n /= 4;
    }
    return n == 1;
}

二，位运算法— O(N)

如果面试要求不能用循环和递归，那就得用位运算了

这个适合2的幂和4的幂两题。

3的幂在第一部分，不用位运算。

（1）2的幂

基本原理是：

一个数 n 是 2的幂，当且仅当 n 是正整数，并且 n 的二进制表示中只包含 1个 1

比如二进制：1 ， 10， 100， 1000, 1000 （即：1， 2， 4， 8， 16）

? 2⁰, 2¹, 2², 2³, 2⁴

所以如果去掉n的这个1，剩下都是0，那么n就是2的幂。

位运算中去掉最低位1的方法（只有一个数的二进制1个1的话，那这个1就是最低位1）：
n & (n - 1)

原理:

假设 n 的二进制表示为 (a1000…0)₂ ，其中a表示1前面还有若干个高位，1就是最低位的这个1，后面还有若干个0.

那么n - 1的二进制就表示为：(a0111…1)₂ ，其中高位的a是不会变的

那么将这两个 (a1000…0)₂ 和(a0111…1)₂ 做与运算，就可以得到(a0000…0)₂

如果n是2的幂，那么这个高位a是不存在的，全是0，因为前面说了，2的幂的二进制表示是只有一个1的，最低位1就是其唯一的一个1，只能是000100000这种，也就是100000.

所以，如果n & (n - 1) 的结果为0，那么n就是2的幂

还有个坑：C++里 ‘==‘符号优先级高于按位与’&’

所以要加上括号：(n & (n - 1)) == 0
那么解答就是：

bool isPowerOfTwo(int n) {
    if(n <= 0) return false;
	return (n & (n - 1)) == 0;
}

（2）4的幂

原理：

首先4的幂肯定是2的幂，但是2的幂不一定是4的幂，比如32。

如果一个数n是2的幂，但不是4的幂，其形式为：4^m x 2。

但是可以发现，如果n是4的幂的话，4^m 对3取模就是1，因为

4^m % 3 == (4 % 3)^m == 1^m == 1.

而4^m x 2这种就是对3取模就为2了。

所以一个数n：如果n是2的幂，而且对3取模为1，那么n就是4的幂

即**(n & (n - 1)) == 0 && n % 3 == 1**

所以答案就是：

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