一. 方法介绍

异或：(相同则为0，不同则为1，比如x^x=0, x^0=x)
位运算是算法里比比较特殊的类型，利用二进制位运算的特性进行一些奇妙的优化和计算。
常用的位运算符号包括：
“^”按位异或； “&”按位与；”|”按位或；”~”取反、”<<”算术左移、”>>”算术右移。
0s和1s分别表示只由0或1构成的二进制数字
x

  1. x^0s=x   x^1s=~x  x^x=0
  2. x&0s=0   x&1s=x   x&x=x
  3. x|0s=x   x|1s=1s  x|x=x
  4. n&(n-1) //去除n的位级表示中最低的那一位，也即从低到高的最先出现的那个1
  5. n&(-n)  //得到n的位级表示中最低的那一位，
  6. x>>=1  //等价于x=x>>1。x的二进制表示右移一位，也即把最右边的一位去掉，然后仍然赋值给x
  7. x<<=1  //x的二进制表示左移1位，也即在最右边添加一个0。
  8. //二进制数左移1位相当于乘以2，右移1位相当于除以2
  10. /*-------异或的相关性质-----*/
  11. //若两个值不相同，则异或结果为1，若两个值相同，则异或结果为0
  12. a^0=a
  13. a^a=0
  14. a^b=b^a
  15. a^b^b=a
  • 可以利用二进制和位运算输出一个数组的所有子集。假设我们有一个长度为 n 的数组，我们可以生成长度为 n 的所有二进制，1 表示选取该数字，0 表示不选取。这样我们就获得了2n个子集。
  • 用位运算判断一个数字是不是2的整数次方：若一个数字n是2的整数次方，则它的二进制一定是0…010…0(只有一个1，并且1的位置不能在最右边)，则n-1的二进制是0…001…1，这两个数求按位与的结果一定是0，则有若n&(n-1)为0，则这个数是2的次方。
  • 用位运算判断一个数字是否是4的整数次方：在满足是2的整数次方的条件下，二进制表示中的1的位置必须为奇数位，因此可以把n和二进制下的1010…101(31位，也即十进制下的1431655765)做按位与，若结果不为0，则说明这个数是4的次方
  • 用n&(n-1)可以判断n中有多少个1，因为n&(n-1)是去除n的位级表示中最先出现“1”的最低的那一位，加上循环一个个去掉，当没有“1”时，也即为0了，可以统计出“1”的个数

二.Leetcode题目

136.只出现一次的数字

题目链接
对于在相同中找不同的题，都可以用二进制的异或方式，原理即为x^x=0, x^0=x.
因为是出现两次，其所有数字按位异或的结果都是0，因此将数组异或，最后留下了的则一定是那个只出现一次的数。

338.比特位计数-(动态规划+二进制)

题目链接
方法一：动态规划-局部区间划分
dp[i]表示数字i的二进制中的1的数目。
dp[0]=0
由观察可知，对于i&(i-1)==0的1的个数一定为1
而对于不为0的，则是其最近的2的次方数再加上一个数，利用last表示最近的2的次方数
dp[i]=dp[i-last]+1;

方法二：动态规划+更细一步的递归规律观察
定义一个数组 dp，其中 dp[i] 表示数字 i的二进制含有 1 的个数。
对于第 i 个数字，如果它二进制的最后一位为 1，那么它含有 1 的个数则为 dp[i-1] + 1；(i的最后一位为1，表示i-1的最后一位为0，则直接相加即可)
如果它二进制的最后一位为 0，那么它含有 1 的个数和其算术右移结果相同，即dp[i>>1]。（若i的最后一位为0，则把0给移除掉得到数和原来的数的二进制1是相同的，并且dp[i>>1]是被缩小过的计算过的数，是已经得到结果的状态）

476.数字的补数-(异或求补)

题目链接
这里要利用一个规律 n^1s=~n。也即找到一个和n有相同位数的全1（比如5的二进制是101，全1是111，也即7），然后异或即可得到n的补数。关键点就在于如何去找到这个相同位数的全1。下面的tmp就是所求的，利用相同位数的全1的一定是大于等于num来结束循环。

  1. int tmp=1;
  2. while (tmp<num) {
  3.     tmp<<=1;
  4.     tmp+=1;
  5. }

693.交替位二进制数-(错位异或)

题目链接
凡是符合题目中的交替位二进制，则必然错位异或的话全是1，所以将错位异或的值+1会生成只有一个二进制1的值(也即是2的整数次方)，再用n^(n-1)进行检查是否是2的整数次方。注意加1可能会超过int型的存储范围，可以用long int来存储错位异或后+1的结果。

面试01.01.判断字符是否唯一

题目链接

  1. 这里用二进制的移位操作。把一个整形的二进制的前26位作为是否存在这个字符的判定，如果是0，则存在，如果是1，在不存在。

    1. bool isUnique(string astr) {
    2.      int mark=0,i,move_bit=0;
    3.      for (i=0;i<astr.size();i++) {
    4.          move_bit=astr[i]-'a';
    5.          if ((mark&(1<<move_bit))!=0){
    6.              return false;
    7.          }else{
    8.              mark=mark|(1<<move_bit);
    9.          }
    10.      }
    11.      return true;
    12.  }

    面试题16.01.交换数字

    题目链接

  2. 运用异或的性质，a^b^b=a，b^a^a=b，则有个公共部分，a^b。，则(a^b)^a=b，(a^b)^b=a，实现不用临时变量的交换。

面试题05.07. 配对交换

题目链接
int型是32位，目标是提取奇数位和偶数位，将奇数位左移一位，将偶数位右移一位，然后相加。
提取奇数位：奇数位全1，0x55555555，
提取偶数位：偶数位全1，0xaaaaaaaa

 int exchangeBits(int num) {
        return (((num & 0x55555555) << 1) | ((num & 0xaaaaaaaa) >> 1));
    }