运算规则

& 按位与：二进制两个都为1则为1，否则为0
| 按位或：二进制两个中有一个为1则为1
^ 按位异或：两个二进制位值相同则为0，否则为1
~ 取反：一个二进制数按位取反，即将0变1，将1变0
<< 左移：将一个数的各二进制位全部左移N位，右补0
>>右移：将一个数的各二进制位右移N位，移到右端的低位被舍弃，对于无符号数， 高位补0

使用技巧

1.消除二进制位中最后一个1

  1. 例子：消除x的最后一位1
  2. x = 1001
  3. x-1 = 1000
  4. & 为都为1则为1
  5. x&(x-1) = 1000

2.判断n是否为2的幂次方

时间复杂度O(1)

  1. // 2的幂次方为 2的x次。所以二进制位中只有一个1存在。
  2. // 消除这个1的话就为0
  3. n&(n-1) == 0?

3.计算一个32位的二进制数有多少个1

  1. // 依次进行最后一个1的消除。直到为0的时候结束循环
  2. // 循环多少次就证明有多少个1
  3. while(n>0){
  4.     n = n&(n-1);
  5.     count++;
  6. }

4.整数A转换为B需要改变多少个bit位

  1. // 使用异或，相同则为0，不同则为1.所以使用异或之后计算1的个数就行

5.二进制进行子集的枚举

从0~2的(n-1)次方的组合。1所在的位置为一个组合

  1. S = {1,2,3}
  2. N bit Combination
  3. 0-> 000 {}
  4. 1-> 001 {1}
  5. 2-> 010 {2}
  6. 3-> 011 {1,2}
  7. 4-> 100 {3}
  8. 5-> 101 {1,3}
  9. 6-> 110 {2,3}
  10. 7-> 111 {1,2,3}

6.a^b^b=a的使用

都相同为0，不同为1
数组中一个数出现了一次，其他的都出现了两次

  1. // 出现两次的值满足a^a = 0
  2. int res = 0;
  3. for(Integer n:nums){
  4.     res ^= n;
  5. }
  6. // 因为其他的两个的都互相消除了，所以剩下的值只有一个出现一次的
  7. return res;


数组中一个数出现了一次，其他的都出现了三次