问题描述

/*
 * bitCount - returns count of number of 1's in word
 *   Examples: bitCount(5) = 2, bitCount(7) = 3
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 40
 *   Rating: 4
 */

解答

int bitCount(int x) {
  int val;
  //制作mask: 0000 0001 0000 0001 0000 0001 0000 0001
  int tmp = 1;
  tmp |= tmp << 8;
  tmp |= tmp << 16;
  //计算每个byte里1的数量
  val = (tmp & x) + (tmp & (x>>1))
  + (tmp & (x>>2)) + (tmp & (x>>3))
  + (tmp & (x>>4)) + (tmp & (x>>5))
  + (tmp & (x>>6)) + (tmp & (x>>7));
  //折叠两次，1的数量保存在低8位中
  val += val >> 16;  
  val += val >> 8;
  return val & 0xff;
}

解题思想

这个解答的思想并不完全是我原创的，参考了DPU 和 流星雨点 。

原创的部分只有在制作mask时[0x01,0x0101,0x01010101]地制作，而不是[0x01,0x0101,0x010101,…,0x01010101]制作。前者比后者少用若干次位运算符。

mask制作好之后，对该二进制串中的byte编号[3, 2, 1, 0]，并行地计算每个byte中1的个数。

然后，将二进制串折叠，分别求byte1 += byte3和byte0 += byte2。

最后将低16位折叠，求byte0 += byte1。

反思

事实上，在看到这种解法之后，我想到的一种减少位运算符的方法：以4bit为单位并行地计算1的数量，而不是以8bit，一个byte为单位。

int bitCount(int x) {
  int val;
  //制作mask: 0001 0001 0001 0001 0001 0001 0001 0001
  int tmp = 1;
  tmp |= tmp << 4;
  tmp |= tmp << 8;
  tmp |= tmp << 16;
  //计算每个byte里1的数量
  val = (tmp & x) + (tmp & (x>>1))
  + (tmp & (x>>2)) + (tmp & (x>>3));
  //折叠两次，1的数量保存在低4位中
  val += val >> 16;  
  val += val >> 8;
  val += val >> 4;
  return val & 0xf;
}

跑了下测试之后发现这种做法是错误的，因为它将结果保存在低4位上，而可以用低4位表示的最大整数为15。而32位整数最多有32个1，至少需要低6位来表示。

所以以一个byte为单位是合适的。以16bit，32bit为单位的话也可行，只是位运算符的数量变多了；事实上以32bit为单位时，解法就退化成最朴素也最容易想到的那一种解法。

int bitCount(int x) {
  int val;
  int tmp = 1;
  val = (tmp & x) + (tmp & (x>>1))
  + ...
  + ...
  + ...
  + (tmp & (x>>30)) + (tmp & (x>>31));
  return val;
}