^ : 按位异或
& : 按位与
| : 按位或
~ : 取反
<< : 算术左移
>> : 算术右移
0s和1s分别表示只由0或1构成的二进制数字

x ^ 0s == x;
x ^ 1s == ~x;
x ^ x == 0;
x & 0s == 0;
x & 1s == 1;
x & x == x;
x | 0s == x;
x | 1s == 1s;
x | x == x;

//n & (n-1)可以去除n的位级表示中最低的那一位
n = 11110100
n & (n-1) == 11110000  
//n & (-n)可以得到n的位级表示中最低的那一位
n = 11110100
n & (-n) == 00000100    

class Solution {
public:
  int hammingWeight(uint32_t n) {
    int ret = 0;
    for (int i = 0; i <= 31; i++) {
      if (n & (1 << i)) {   //检查每一位是否为1   从低位到高位检查
        ret++;
      }
    }
    return ret;
  }
};

class Solution {
public:
  int hammingWeight(uint32_t n) {
    int ret = 0;
    while (n) {
      n = n & (n - 1);    //n & (n - 1)    每次把最低位的1  变成  0
      ret++;
    }
    return ret;
  }
};

class Solution{
public:
    int hammingDistance(int x, int y){
        int diff = x ^ y;  //异或
        int res = 0;
        while(diff){
            res += diff & 1;  //看低位是否为1
            diff >>= 1;       //右移
        }
        return res;
    }
};

class Solution{
public:
    int hammingDistance(int x, int y){
        int diff = x ^ y;  //异或
        int res = 0;
        while(diff){
            diff &= diff - 1;  //从低位到高位将1变0
            res++;      
        }
        return res;
    }
};

class Solution {
public:
  uint32_t reverseBits(uint32_t n) {
    uint32_t res = 0;
    for (int i = 0; i <= 31; i++) {
      res <<= 1;     //扩充一位
            res |= n & 1;  //扩充位上填数
            n >>= 1;      //舍弃低位
    }
    return res;
  }
};

class Solution {
public:
  uint32_t reverseBits(uint32_t n) {
    uint32_t rev = 0;
    for (int i = 0; i <= 31 && n > 0; i++) {
      rev = rev | ((n & 1) << (31 - i));     //|相当于保留1
      n >>= 1;                               //n右移一位
    }
    return rev;
  }
};

class Solution {
public:
    uint32_t reverseBits(uint32_t n) {
        n = (n >> 16) | (n << 16);
        n = ((n & 0xff00ff00) >> 8) | ((n & 0x00ff00ff) << 8);   // 00000000111111110000000011111111
        n = ((n & 0xf0f0f0f0) >> 4) | ((n & 0x0f0f0f0f) << 4);   // 00001111000011110000111100001111
        n = ((n & 0xcccccccc) >> 2) | ((n & 0x33333333) << 2);   // 00110011001100110011001100110011
        n = ((n & 0xaaaaaaaa) >> 1) | ((n & 0x55555555) << 1);   // 01010101010101010101010101010101
        return n;
    }
};

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int ret = 0;
        for (auto e: nums) ret ^= e;      //两个相同的值做异或结果为0  任何数和0异或等于它本身
        return ret;
    }
};

class Solution {
public:
  int singleNumber(vector<int>& nums) {
    for (int i = 1; i < nums.size(); i++) {
      nums[0] ^= nums[i];
    }
    return nums[0];
  }
};

class Solution {
public:
    vector<int> singleNumber(vector<int>& nums) {
        unsigned int target = 0;   //unsigned不能少
        // 一对相同的数字异或为0
        // 所以target为两个只出现了一次的元素的异或
        for (auto n: nums) {
            target ^= n;
        }
        // 因为两数不同，lowbit必然不为0
        // 物理意义就是两个不同的数字不同的最低的位在哪
        int lowbit = target & (-target);
        int a1 = 0;
        int a2 = 0;
        // 重复上述的过程，但是将nums按照lowbit为1或者为0分类
        // 则两个数必然被分到不同的类目；而相同的数字一定在同一个类目
        // 所以按类目分别异或就可以得到两个不同的数字
        for (auto n: nums) {
            if (n & lowbit) {
                a1 ^= n;
            } else {
                a2 ^= n;
            }
        }
        return {a1, a2};
    }
};

//时间复杂度：O(1)
//空间复杂度：O(1)
class Solution {
//private:
  //static constexpr int BIG = 1 << 30;   //最大的2的幂数  即BIG=2^30
public:
  bool isPowerOfTwo(int n) {
    return n > 0 && 1073741824 % n == 0;
  }
};

class Solution {
public:
  bool isPowerOfTwo(int n) {
    return n > 0 && (n & (n - 1)) == 0;   //抹掉1，判断是否等于0
  }
};

class Solution {
public:
  bool isPowerOfTwo(int n) {
    return n > 0 && (n & -n) == n;    //提取1，判断是还等于n，等于说明原来的数只有一个1  
  }
};

bool isPowerOfFour(int n){
  return n > 0 && !(n & (n - 1)) && (n & 1431655765);  //与10101..101的十进制数按位与
};

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

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

class Solution {
public:
    int maxProduct(vector<string>& words) {
    unordered_map<int, int> map;
        int res = 0;
        for(const string& word : words){
      int mask = 0;
            int size = word.size();
            for(const char& c : word){ //求到该单词对应的长度为26的二进制数字
                mask |= 1 << (c - 'a');
            }
            map[mask] = max(map[mask], size); //max(ab, aab)  最优，避免了重复计算
            for(const auto& [h_mask, h_len] : map){
                if(!(mask & h_mask)){ //如果两个字符串含有重复数字，它们的二进制表示按位与不为0
                    res = max(res, size * h_len);
                }
            }
        }
        return res;
    }
};

class Solution {
public:
    int count (int i){
        int res = 0;
        while(i){
            i &= (i - 1);
            res++;
        }
        return res;
    }
    vector<int> countBits(int n) {
        vector<int> res(n+1);
        for(int i = 0; i <= n; i++){
            res[i] = count(i);
        }
        return res;
    }
};

class Solution {
public:
    vector<int> countBits(int n) {
        vector<int> bits(n + 1);
        for (int i = 1; i <= n; i++) {
            bits[i] = bits[i & (i - 1)] + 1;
        }
        return bits;
    }
};

class Solution {
public:
    int missingNumber(vector<int>& nums) {
        int res = 0;
        int n = nums.size();
        for (int i = 0; i < n; i++) {
            res ^= nums[i];
        }
        for (int i = 0; i <= n; i++) {
            res ^= i;
        }
        return res;
    }
};

class Solution {
public:
    char findTheDifference(string s, string t) {
        int res = 0;
        for(auto i : s)
            res ^= i;
        for(auto i : t)
            res ^= i;
        return res;
    }
};

class Solution {
public:
  char findTheDifference02(string s, string t) {
    int s_sum = 0;
    int t_sum = 0;
    for (char ch : s) 
      s_sum += ch;
    for (char ch : t)
      t_sum += ch;
    return t_sum - s_sum;
  }
};  

class Solution {
public:
    bool hasAlternatingBits(int n) {
        long a = n ^ (n >> 1);  //如果n交替，则a的二进制全为1
        return (a & (a + 1)) == 0;
    }
};

class Solution {
public:
    int findComplement(int num) {
        long a = 1;
        while(true){
            if(num >= a){
                a <<= 1; // 等价于 a *= 2;
            }else{
                return a - num - 1;
            }
        }
    }
};