常用技巧

位运算是算法里比较特殊的一种类型，他们利用二进制位运算的特性进行一些奇妙的优化和计算。常用的位运算符包括：“^”异或、“&”与、“|”或、“~”非、算数左移“<<”，算数右移“>>”
n&(n-1)可以去掉最低一位，
n&(-n)可以得到二进制数的最后一个1所表示的二进制

基础

461. 汉明距离（计算两数二进制位不同的 个数）

  1. class Solution {
  2. public:
  3.     int hammingDistance(int x, int y) {
  4.     int a=x^y;
  5.     int sum=0;
  6.     while(a!=0){
  7.         sum+=a&1;
  8.         a=a>>1;
  9.     }
  10.     return sum;
  11.     }
  12. };

190. 颠倒二进制位（二进制位前后颠倒）

用新的数据来存储，一个左移，一个右移

  1. class Solution {
  2. public:
  3.     uint32_t reverseBits(uint32_t n) {
  4.         uint32_t ans = 0;
  5.         for(int i = 0; i < 32; ++i){
  6.             ans <<= 1;
  7.             ans += n & 1;
  8.             n >>= 1;
  9.         }
  10.         return ans;
  11.         cout<<ans<<endl;
  12.     }
  13. };
  14. //定义一个 32 位int ans来存储结果，每次左移，然后原数据右移

136. 只出现一次的数字（异或）

  1. class Solution {
  2. public:
  3.     int singleNumber(vector<int>& nums) {
  4.         int ans = 0;
  5.         for(const int & num : nums){
  6.             ans^=num;
  7.         }
  8.         return ans;
  9.     }
  10. };

693. 交替位二进制数

遍历

  • 注意优先级问题

    1. class Solution {
    2. public:
    3.   bool hasAlternatingBits(int n) {
    4.       int pre = n&1;  
    5.       n = n >> 1;
    6.       while(n) {
    7.           if(pre == (n&1)) return false;
    8.           pre = n&1;
    9.           n = n >> 1;
    10.       }
    11.       return true;
    12.   }
    13. };

    异或

    对输入 n 的二进制表示右移一位后，得到的数字再与 n 按位异或得到 a。当且仅当输入 n 为交替位二进制数时，a 的二进制表示全为 1（不包括前导 0）。这里进行简单证明：当 a 的某一位为 1 时，当且仅当 n 的对应位和其前一位相异。当 a 的每一位为 1 时，当且仅当 n 的所有相邻位相异，即 n 为交替位二进制数。

    1. class Solution {
    2. public:
    3.   bool hasAlternatingBits(int n) {
    4.       long a = n ^ (n >> 1);
    5.       return (a & (a + 1)) == 0;
    6.   }
    7. };

    二进制特性

    342. 4的幂（log以及特性）

    log

  • double fmod(double x, double y)返回x除以y的余数

    1. class Solution {
    2. public:
    3.   bool isPowerOfFour(int n) {
    4.       double a ;
    5.       a = log10(n)/log10(4);
    6.       return fmod(a,1)==0;
    7.   }
    8. };

    二进制数特性

    如果这个数是2的整数次方。那么它的二进制为1的个数只有一个。如果这个数是4的整数次方，那么二进制中表示1的位置一定是奇数位。
    n&n-1可以去除位级中表示最低的一位。
    1431655765是所有奇数位置1的结果

    1. class Solution {
    2. public:
    3.   bool isPowerOfFour(int n) {
    4.       return n > 0&& !(n &(n-1))&&(n&1431655765);
    5.   }
    6. };

    318. 最大单词长度乘积（二进制占位）

    思想：通过二进制的方式来表达这个a-z的字符在字符串中是否存在。

  • 为了方便遍历，使用hash表来存储数据，key为字符串在二进制数中的位置，value为相同占位字符串的最大长度

  • 通过一个26位的二进制数来表示，字符a-z在字符串中存在的情况

    1. class Solution {
    2. public:
    3.   int maxProduct(vector<string>& words) {
    4.       unordered_map <int , int> hash;//建立哈希表，两个值分别为mask和最大长度
    5.       int ans = 0;//最大值
    6.       for(const string &word : words){
    7.           int mask = 0, size = word.size();//size是字符串的长度
    8.           for(const char &c : word){
    9.               mask |= 1 <<(c - 'a');//此处的等式右边表示每个字母对应的二进制数表示形式
    10.               //此处的mask就代表着前一个字符串与现在的字符串相或的结果，如果有相同的字母，或为1
    11.           }
    12.           hash[mask] = max(hash[mask], size);//构建一个哈希表，存储最大值
    13.           for(const auto&[h_mask,h_len]:hash){
    14.               if(!(mask & h_mask)){
    15.                   ans = max(ans, size*h_len);
    16.               }
    17.           }
    18.       }
    19.       return ans;
    20.   }
    21. };

    338. 比特位计数（动态规划）

    巧妙，只能说巧妙
    分为两种情况，最低位为1和最低位为0。

  • 最低位为1的话就代表i-1的最低位为零，直接dp[i-1]即可

  • 最低位为0的话，经过移位1的数量不变，因此直接dp[i>>1]即可 ```cpp class Solution { public: vector countBits(int num) {
       vector<int> dp(num+1, 0);
   for(int i = 1; i <= num; ++i)
       dp[i] = i & 1? dp[i-1] + 1: dp[i>>1];//往左移动一位相当于变小，因为最后一位是0所以1的个数并没有发生改变
   return dp;
    }

};

<a name="vQDvN"></a>
### [268. 丢失的数字](https://leetcode-cn.com/problems/missing-number/)（只出现一次数字的变形题）

- 题目让求一个数组中没有出现的0~n中的数字是那一个
- 这个数组加上0~n的所有数字。就是求只出现一次的数字的题目了
```cpp
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;
    }
};

693. 交替位二进制数（善用位运算符）

class Solution {
public:
    bool hasAlternatingBits(int n) {
        int a = 1&n;
        n >>= 1;
        while(n>0){
            if((n&1) == a) return false;
            a = 1&n;
            n >>= 1;
        }
        return true;
    }
};

476. 数字的补数（注意条件）

  • 最高有效位，左边的为0的二进制位不应该参与运算
  • 因此先求得最高有效位在哪里，然后进行设置掩码mask全为1，进行异或运算即可取反。
    class Solution {
public:
  int findComplement(int num) {
      int highbit = 0;
      for (int i = 1; i <= 30; ++i) {
          if (num >= (1 << i)) {
              highbit = i;
          }
          else {
              break;
          }            
      }//求为1的最高位  highbit
      int mask = (highbit == 30 ? 0x7fffffff : (1 << (highbit + 1)) - 1);
      return num ^ mask;
  }
};