查找32位整数的二进制表示中1的个数

solution1.md

方案1：

int solution1(int x) {
  int count = 0;
  for (int i=0; i<32; i++) {
    if (i & 1 == 1) {
      count++''
    }
  }
  return count;
}

没啥好说的。

solution2.md

方案2:

int solution2(int x) {
  int count = 0;
  for (; x!=0; count++) {
    x &= x-1;
  }
}

这里x &= x - 1是关键，每次减一，都会将最后一个1变为0，因此循环的次数就是1的个数。例如，x=7:

loop begin
x = 0x111
x - 1 = 0x110
x & (x - 1) = 0x111 & 0x110 = 0x110
x = 0x110
x - 1 = 0x101
x & (x - 1) = 0x110 & 0x101 = 0x100
x - 1 = 0x011
x & (x - 1) = 0
loop end

solution3.md

方案3：

int solution3(int int x) {
  int mask1  = 0x55555555;
  int mask2  = 0x33333333;
  int mask4  = 0x0f0f0f0f;
  int mask8  = 0x00ff00ff;
  int mask16 = 0x0000ffff;

  x = (x & mask1 ) + (x>>1  & mask1 );
  x = (x & mask2 ) + (x>>2  & mask2 );
  x = (x & mask4 ) + (x>>4  & mask4 );
  x = (x & mask8 ) + (x>>8  & mask8 );
  x = (x & mask16) + (x>>16 & mask16);
  return x;
}

这个方案可以看作是一种归并策略。

0x55555555 = 01010101010101010101010101010101B
0x33333333 = 00110011001100110011001100110011B
0x0f0f0f0f = 00001111000011110000111100001111B
0x0000ffff = 00000000000000001111111111111111B

将上面的MASK写成二进制表示，可以看出MASK的作用都是为了x划分成长度固定的分块，分别计算每个分块中1的个数，然后在合并计算结果。

x = (x & mask1 ) + (x>>1  & mask1 );

以2位分块，计算x中每两位中1的个数。由于每个分块中1的个数最多为2，所以。这里，不要计较x的值到底是什么含义，这里的x已经被分块处理了。

x = (x & mask2 ) + (x>>2  & mask2 );

以4位分块，将上一次的计算结果归并，每两个分块的计算结果合到一个稍大的分块中。

x = (x & mask4 ) + (x>>4  & mask4 );

以8位分块，将上一次的计算结果归并，每两个分块的计算结果合到一个稍大的分块中。

x = (x & mask8 ) + (x>>8  & mask8 );

以16位分块，将上一次的计算结果归并，得到最终结果。