计算汉明权重算法 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位整数的汉明权重计算；
Original: https://www.cnblogs.com/Albert-lihai/p/16650973.html
Author: Albert_禄遥
Title: 经典算法学习-计算汉明权重 SWAR(SIMD within a register)
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/644205/
转载文章受原作者版权保护。转载请注明原作者出处！