与 &

  1. 最常见的题目： 识别二进制中数字的个数 n&(n-1)
  2. 检查数字是不是全为 1：return tmp&(tmp+1)==0
  3. Python 需要 (A & 0xffffffff) 来应对负数：
    • 正常整形数在内存中是以 补码 的形式存放的，输出的时候也是 补码。
    • Python 中负数输出是：在原码的二进制前面加上一个负号：bin(-3)=-0b11
      • 对于 bin(x)（x 为 十进制负数），输出的是它的原码的二进制表示加上一个负号
      • 对于 bin(x)（x 为 十六进制负数），输出的是对应的二进制表示
    • 所以需要先得到一个十六进制数，然后再转换为二进制

异或 ^

  1. 交替位二进制数
    1. # 交替使得 1 0 相对
    2. tmp=n^(n>>1)
    3. # 检查数字是不是全为 1
    4. return tmp&(tmp+1)==0

原码、反码、补码

  1. 原码 + 反码 相加的和是 2**n-1

  2. Python 生成的原码

    1. binNumberStr=bin(N)[2:]
    2. # 0b 111 bin(7)

  3. 利用原码求反码

    1. class Solution {
    2. public:
    3.  int bitwiseComplement(int N) {
    4.      if(N==0){return 1;}
    6.      int tmp1=1;
    7.      int tmp2=N;
    8.      while(tmp2>0){
    9.          N^=tmp1;
    10.          tmp1=tmp1<<1;
    11.          tmp2=tmp2>>1;
    12.      }
    13.      return N;
    14.  }
    15. };
    1. class Solution {
    2. public:
    3.  int bitwiseComplement(int N) {
    4.      int tmp=2;
    5.      while(tmp<=N){tmp<<=1;}
    6.      return tmp-1 -N;
    7.  }
    8. };

按位取反

Python 中 ~x = -(x+1) 原理：

  • ~9

转二进制：0 1001
计算补码：0 1001
按位取反：1 0110
要知道它所表达的数是多少，需要转换为原码
末位加一：1 1010
符号位为1是负数，即 -10

  • ~ -9

转二进制：1 1001
计算补码：1 0111
按位取反：0 1000
要知道它所表达的数是多少，需要转换为原码
正数的补码和原码相同，仍为：0 1000，即 8

组合

  1. 使用位运算计算加法：

    • Step1: a^b，完成不进位加法
    • Step2: a&b，完成进位的运算
    • Step3: 把step2左移一位，模拟正常加法的向前进一位
      1. class Solution {
      2. public:
      3. int add(int a, int b) {
      4.    if(b==0){return a;}
      5.    int step1=0,step2=0,step3=0;
      6.    while(b!=0){
      7.        step1=a^b;
      8.        step2=a&b;
      9.        step3=(unsigned int)step2<<1;
      10.        a=step1;
      11.        b=step3;
      12.    }
      13. return step1;
      14. }
      15. };

  2. 汉明距离

异或 和 number&(number-1) 就可以解决了