LeetCode 1780. 判断一个数字是否可以表示成三的幂的和（位运算）

示例 1：
输入：n = 12
输出：true
解释：12 = 3^1 + 3^2

示例 2：
输入：n = 91
输出：true
解释：91 = 3^0 + 3^2 + 3^4

示例 3：
输入：n = 21
输出：false
 
提示：
1 <= n <= 10^7

class Solution {
public:
    bool checkPowersOfThree(int n) {
        int s = (1<<15);
        vector<int> pow3(16, 1);
        for(int i = 1; i <= 15; i++)
            pow3[i] = pow3[i-1]*3;
        for(int i = 0; i <= s; i++) 
        {	// 系数是 i 
            int num = 0;
            for(int j = 0; j <= 15; j++)
            {
                if(1&(i>>j))//第 j 位系数 是 1
                    num += pow3[j];
            }
            if(num == n)
                return true;
        }
        return false;
    }
};

class Solution {
public:
    bool checkPowersOfThree(int n) {
        int s = (1<<15);
        vector<int> pow3(16, 1);
        for(int i = 1; i <= 15; i++)
            pow3[i] = pow3[i-1]*3;
        for(int i = 15; i >= 0; --i)
        {	
            if(n >= pow3[i])
                n -= pow3[i];
        }
        return n==0;
    }
};