计算汉明权重算法 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位整数的汉明权重计算;