位运算

6.位运算

主要思想：

• 获取一个数的二进制的第k位：x>>k & 1，将x右移k位即第k位就移动到最低有效位，每次右移后的数与1做按位与运算，只会保留最低有效位即第k位的二进制数。如x=10111，x>>2，得x=101，与1按位与，即101&001=001，最后就得到1

• 获取一个数的二进制的最后一位1：lowbit(x)= x & -x

  例如 x = 1010 lowbit(x) = 10；x = 101000 lowbit(x) = 1000

  lowbit运算的原理是，x & -x，由于-x采用补码表示，它等于对x的原码取反再加1，即-x = ~x + 1

  比如 x 的二进制表示是：100101000，对x取反得011010111，加1得011011000（即-x），经过x & (~x + 1)，x的最后一位1，被保留了下来，这个位置后面，两个数全是0；这个位置前面，两个数是取反，做与运算后也全为0，即最终结果就为000001000

  lowbit的最简单的应用：统计x的二进制表示中，1的个数。具体的实现方式是：每次对x做lowbit运算，并将运算结果从x中减去。循环做下去，直到x被减为0，一共减了多少次，x中就有多少个1。

  AcWing801.二进制中1的个数

  #include <iostream>
  using namespace std;
   
  //找到x最后一个1开始的二进制数
  int lowbit(int x){
      return x & -x;
  }
   
  int mian(){
  	int n;
      cin>>n;
      while(n--){
          int x;
          cin>>x;
          int res=0;
          while(x) x-=lowbit(x),res++;//每次减去x最后一位1
      }
      cout<<res;
      return 0;
  }