Leecode 位运算

231. 2的幂

三种位运算方法
因为2次幂均为 1000000形式，n-1即为0111111111形式
负数为源码补码加一 1000000000 对应负数

return n>0 && (n&n-1)==0;
return n>0 && (n&-n)==n;
return n>0 && (1<<30)%n==0;

判断质数

## 常规算法
bool isprimer(int n){
    for(int i = 2; i<n-1 ;i++){
          if(n%i == 0) return 0;
  }
    return 1;
}
## 改进算法，采用sqrt(n)

bool is_prime2(unsigned long long n) { //unknow
    long long stop = sqrt(n) + 1;
    if (n == 2) {
        return true;
    }
    if (n % 2 == 0) {
        return false;
    }
    for (int i = 3; i <= stop; i += 2) {
        if (n % i == 0) {
            return false;
        }
    }
    return true;
}

762. 二进制表示中质数个计算置位

for (int k = i;k; k >>= 1) nn += k & 1;   # 判断二进制个数
int countPrimeSetBits(int L, int R) {
        unordered_set<int> pp({2,3,5,7,11,13,17,19,23,29});
        int res = 0;
        for (int i = L; i <= R; i++) {
            int nn = 0;
            for (int k = i;k; k >>= 1) nn += k & 1;
            //cout << nn << endl;
            if (pp.count(nn)) res++;
            //cout << res << endl;
        }
        return res;

136. 只出现一次的数字

输入: [4,1,2,1,2]
输出: 4

#运用异或解决
for(auto x:nums) return res^=x;
#消消乐

476. 数字的补数

输入: 5
输出: 2
解释: 5 的二进制表示为 101（没有前导零位），其补数为 010。所以你需要输出 2 。

#运用位运算
int res=0,t=0;
while(num){
    res+= !(num&1)<<t;
    t++;
    num>>1;
}
return res;

137. 只出现一次的数字 II

统计32位 1的个数，模3余一保留即为单独数字