经典算法学习-计算汉明权重 SWAR(SIMD within a register)

计算汉明权重算法 SWAR(SIMD within a register)

参考文章:

[1] 简书：计算汉明权重的SWAR（SIMD within a Register）算法https://www.jianshu.com/p/b0db1f072a66

[2]维基百科：SWAR https://en.wikipedia.org/wiki/SWAR

[3]Hacker's Delight[M].Henry S. Warren

简述：

这个专栏记录一些看到的经典算法，既然想不出来，只能努力去学习；

算法目标：

计算二进制串汉明权重；

汉明权重，一个二进制子串中1的个数;

!

实现思想：

分治算法,

• 先将两个比特视为一组，共16组，计算每组有多少个1；

  i = (i & 0x55555555) + ((i >> 1) & 0x55555555);
  

• 通过上一句，已经得到了在16组范围在[0,2]之间的结构，接下来在此基础上将每4个比特视为一组，判断其中有多少个1;

  i = (i & 0x33333333) + ((i >> 2) & 0x33333333)
  

• 我们已经得到了8组范围在[0, 4]之间的结果，接下来在此基础上将每8个比特（即上一步的每两组）视为一组，一共4组，计算每组中有多少个1。

  i = (i & 0x0F0F0F0F) + ((i >> 4) & 0x0F0F0F0F)
  

• 接下来继续依照分治思想，两两合并即可

  public static int bitCount(int i) {
      i = (i & 0x55555555) + ((i >> 1) & 0x55555555);
      i = (i & 0x33333333) + ((i >> 2) & 0x33333333);
      i = (i & 0x0F0F0F0F) + ((i >> 4) & 0x0F0F0F0F);
      i = (i & 0x00FF00FF) + ((i >> 8) & 0x00FF00FF);
      i = (i & 0x0000FFFF) + ((i >> 16) & 0x0000FFFF);
      return i;
  }
  

  这样，只需要单个寄存器和时间复杂度为O(1)就可以实现对32位整数的汉明权重计算；