时间：   |   分类：     |   阅读： 277 字 ~2分钟

LeetCode题191是算整数中比特1的个数，即汉明重量或汉明权重。

汉明重量

汉明重量是一串符号中非零符号的个数。因此它等同于同样长度的全零符号串的汉明距离。在最为常见的数据位符号串中，它是1的个数。 汉明重量是以理查德·卫斯里·汉明的名字命名的，它在包括信息论、编码理论、密码学等多个领域都有应用。

算法

位移实现

我自己的实现就是这种。通过判别n是否为0作为循环退出条件，如果n为0x1的话就位移一次，可是n为0x80000000还是需要位移32次。

public int hammingWeight(int n) {
  int res = 0;
  while(n!=0) {
    res+= (n & 0x1);
    n >>>=1;
  }
  return res;
}

n & (n-1)实现

public int hammingWeight(int n) {
  int res = 0;
  for(;n!=0;n = n & (n-1)) {
    res++;
  }
  return res;
}

减1操作将最右边的符号从0变到1，从1变到0，与操作将会移除最右端的1。如果最初n有X个1，那么经过X次这样的迭代运算，n将减到0。n& (n-1)实现在大多数比特为0的情况下是效率最高的。 此外n & (n-1)常用于判断数是否为2的幂数（LeetCode题231）：

     ----- binary ----
 n      n    n-1   n&(n-1)
--   ----   ----   -------
 0   0000   0111    0000 *
 1   0001   0000    0000 *
 2   0010   0001    0000 *
 3   0011   0010    0010
 4   0100   0011    0000 *
 5   0101   0100    0100
 6   0110   0101    0100
 7   0111   0110    0110
 8   1000   0111    0000 *
 9   1001   1000    1000
10   1010   1001    1000
11   1011   1010    1010
12   1100   1011    1000
13   1101   1100    1100
14   1110   1101    1100
15   1111   1110    1110

JDK实现

java.lang.Integer类中bitCount函数实现：

public static int bitCount(int i) {
  // HD, Figure 5-2
  i = i - ((i >>> 1) & 0x55555555);
  i = (i & 0x33333333) + ((i >>> 2) & 0x33333333);
  i = (i + (i >>> 4)) & 0x0f0f0f0f;
  i = i + (i >>> 8);
  i = i + (i >>> 16);
  return i & 0x3f;
}

算法分析如下：

  • 对位长为2的数计算比特1的个数： nn»>1比特1计数 n-(n»>1)000000010001100101110110 这样，对位长为2的数进行如上计算后，2位数内存放的就是原来比特1的个数了。一个整数为32位，按2位分成16组，对于i»>1操作，前一组末位为1的话就会串入后一组，所以要对每组同0x01相与，对于整个32位整数即与0x55555555相与。
  • 上一步中对一个整数比特1的计数是分散到16组位长为2的数内了，这一步是收缩到8组位长为4的数内。位长为4的数，如果想计算前两位和后两位的和，可以通过(i&0x3) +((i»>2)&0x3)实现。0x3对应上一步的16组位长为2的数，而对整数而言即与0x33333333相与。
  • 这一步是将上一步的结果收缩到4组位长为8的数内位长为8的数，如果想计算前四位和后四位的和，可以通过(i+(i»>4))&0xf实现（注：位长为8的数最多有8个比特1，所以先对两部分用0xf，还是最后对结果用0xf无所谓）。0xf对应上一步的8组位长为4的数，而对整数而言即与0x0f0f0f0f相与。
  • 这一步是将上一步的结果收缩到2组位长为16的数内
  • 这一步是将上一步的结果收缩到1组位长为32的数内
  • 一个整数最多32个比特1，32为0b00100000，所以最后用0x3f（即0b00111111）过滤一下。而Long类中用0x7f过滤。像WIKI中popcount_1实现每一步都过滤到位，最后就无需过滤，每一步的中间结果更加清晰、易于理解。
    public static int popcount_1(int i) {
  i = (i  & 0x55555555) + ((i >>> 1) & 0x55555555);
  i = (i & 0x33333333) + ((i >>> 2) & 0x33333333);
  i = (i + (i >>> 4)) & 0x0f0f0f0f;
  i = (i + (i >>> 8)) & 0x00ff00ff;
  i = i + (i >>> 16) & 0x0000ffff;
  return i;
}

资料

WIKI: Hamming weight
Aggregate Magic Algorithms 优化汉明重量算法及其它算法解释（附源代码）
Bit Twiddling Hacks 带有源代码的几种汉明重量计算方法

0%