位运算技巧：

1. 获取二进制中最右边的1：x & (-x)
2. 将二进制中最右边的1设置为0： x & (x -1)
3. 解释链接
4. 获取最低位的1：x & 1

剑指 Offer 15. 二进制中1的个数

写法一：通过移位统计1的个数

class Solution {
public:
    int hammingWeight(uint32_t n) {
        int res = 0;
        while(n)
        {
            res += n & 1;
            n >>= 1;
        }
        return res;
    }
};

写法二：消去1，直到不能消为止

class Solution {
public:
    int hammingWeight(uint32_t n) {
        int res = 0;
        while(n)
        {
            n &= n - 1; // 技巧：n &= n - 1，消去n最右边的1
            res ++;
        }
        return res;
    }
};

231. 2的幂

前置知识：2的幂只会有1个1

class Solution {
public:
    bool isPowerOfTwo(int n) {
        // 2的幂只会有1个1， n & (n - 1)消去最右边的1，O(1)
        return n > 0 && (n & (n - 1)) == 0; // 注意运算符的优先级
    }
};

326. 3的幂

没别的特点，一直除3

class Solution {
public:
    bool isPowerOfThree(int n) {
        if(n < 1) return false; // 0特判
        while(n % 3 == 0){ // 先判断，不然5/3 = 1
            n /= 3;
        }
        return n == 1;
    }
};

进阶：换底公式,由题意得 $n = 3^x, x = log_3n = \frac{log_{10}n} {log_{10}3},x 为整数$

class Solution {
public:
    bool isPowerOfThree(int n) {
        if(n < 1) return false; // 0特判
        // 换底公式
        double a = log10(n) / log10(3); // 换底
        return a == floor(a); // floor(a) 向上取整
    }
};

342. 4的幂

由题意得 $ n = 4^x = 2 ^{2x} = 2 ^ k,n必然也是2的幂次$
n%3=(3+1)%3 = 1,综上，n为4的幂有：n为2的幂且%3=1

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

504. 七进制数

进制转换

class Solution {
public:
    string convertToBase7(int num) {

        if(num == 0) return "0";
        // 短除法，十进制转k进制
        string res;
        bool f = 0;
        if(num < 0) f = 1, num = -num;
        while(num){
            res += num % 7 + '0';
            num /= 7;
        }
        if(f) res += '-';
        reverse(res.begin(),res.end());


        return res;
    }
};