位运算求解LeetCode--3的幂

3的幂

https://leetcode.cn/problems/power-of-three/description/

思路

方法1：如果一个数是3的幂，那么在int范围内，它一定是1162261467的因数（1162261467是int范围内3的最大幂，3的19次幂），所以只需判断该数字是否是1162261467的因数即可

方法2：如果并不知道int范围内3的最大幂值，可以使用循环求解。不断将该数字除以3，直到它不再是3的倍数，判断是否为1，若为1则是3的幂，不为1则不是

代码

方法1：

class Solution {
public:
    bool isPowerOfThree(int n) {
        return n>0 && 1162261467%n==0;
    }
};

方法2： 

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

复杂度

方法1时间复杂度：O(1)

方法2时间复杂度：O(logn)

本题算法核心

在一定范围内，一个数字的所有幂值是该数字最大幂值的因数。