[科普中国]-汉明重量

汉明重量是一串符号中非零符号的个数。因此它等同于同样长度的全零符号串的汉明距离。在最为常见的数据位符号串中，它是1的个数。

汉明重量是以理查德·卫斯里·汉明的名字命名的，它在包括信息论、编码理论、密码学等多个领域都有应用。1

SWAR算法“计算汉明重量”第一步：
计算出来的值i的二进制可以按每2个二进制位为一组进行分组，各组的十进制表示的就是该组的汉明重量。

第二步：
计算出来的值i的二进制可以按每4个二进制位为一组进行分组，各组的十进制表示的就是该组的汉明重量。

第三步：
计算出来的值i的二进制可以按每8个二进制位为一组进行分组，各组的十进制表示的就是该组的汉明重量。

第四步：
i * (0x01010101)计算出汉明重量并记录在二进制的高八位，>>24语句则通过右移运算，将汉明重量移到最低八位，最后二进制对应的的十进制数就是汉明重量。

算法时间复杂度是O（1）的。

相关代码

// 计算32位二进制的汉明重量int32_t swar(int32_t i){ i = (i & 0x55555555) + ((i >> 1) & 0x55555555); i = (i & 0x33333333) + ((i >> 2) & 0x33333333); i = (i & 0x0F0F0F0F) + ((i >> 4) & 0x0F0F0F0F); i = (i * (0x01010101) >> 24); return i}实现在密码学以及其它应用中经常需要计算数据位中1的个数，针对如何高效地实现人们已经广泛地进行了研究。一些处理器使用单个的命令进行计算，另外一些根据数据位向量使用并行运算进行处理。对于没有这些特性的处理器来说，已知的最好解决办法是按照树状进行相加。例如，要计算二进制数A=0110110010111010中1的个数，这些运算可以表示为图一：

这里的运算是用C语言表示的，所以X >> Y表示X右移Y位，X & Y表示X与Y的位与，+表示普通的加法。基于上面所讨论的思想的这个问题的最好算法列在这里：

//types and constants used in the functions below typedef unsigned __int64 uint64; //assume this gives 64-bitsconst uint64 m1 = 0x5555555555555555; //binary: 0101...const uint64 m2 = 0x3333333333333333; //binary: 00110011..const uint64 m4 = 0x0f0f0f0f0f0f0f0f; //binary: 4 zeros, 4 ones ...const uint64 m8 = 0x00ff00ff00ff00ff; //binary: 8 zeros, 8 ones ...const uint64 m16 = 0x0000ffff0000ffff; //binary: 16 zeros, 16 ones ...const uint64 m32 = 0x00000000ffffffff; //binary: 32 zeros, 32 ones ...const uint64 hff = 0xffffffffffffffff; //binary: all onesconst uint64 h01 = 0x0101010101010101; //the sum of 256 to the power of 0,1,2,3... //This is a naive implementation, shown for comparison,//and to help in understanding the better functions.//It uses 24 arithmetic operations (shift, add, and).int popcount_1(uint64 x) { x = (x & m1 ) + ((x >> 1) & m1 ); //put count of each 2 bits into those 2 bits x = (x & m2 ) + ((x >> 2) & m2 ); //put count of each 4 bits into those 4 bits x = (x & m4 ) + ((x >> 4) & m4 ); //put count of each 8 bits into those 8 bits x = (x & m8 ) + ((x >> 8) & m8 ); //put count of each 16 bits into those 16 bits x = (x & m16) + ((x >> 16) & m16); //put count of each 32 bits into those 32 bits x = (x & m32) + ((x >> 32) & m32); //put count of each 64 bits into those 64 bits return x;} //This uses fewer arithmetic operations than any other known //implementation on machines with slow multiplication.//It uses 17 arithmetic operations.int popcount_2(uint64 x) { x -= (x >> 1) & m1; //put count of each 2 bits into those 2 bits x = (x & m2) + ((x >> 2) & m2); //put count of each 4 bits into those 4 bits x = (x + (x >> 4)) & m4; //put count of each 8 bits into those 8 bits x += x >> 8; //put count of each 16 bits into their lowest 8 bits x += x >> 16; //put count of each 32 bits into their lowest 8 bits x += x >> 32; //put count of each 64 bits into their lowest 8 bits return x &0xff;} //This uses fewer arithmetic operations than any other known //implementation on machines with fast multiplication.//It uses 12 arithmetic operations, one of which is a multiply.int popcount_3(uint64 x) { x -= (x >> 1) & m1; //put count of each 2 bits into those 2 bits x = (x & m2) + ((x >> 2) & m2); //put count of each 4 bits into those 4 bits x = (x + (x >> 4)) & m4; //put count of each 8 bits into those 8 bits return (x * h01)>>56; //returns left 8 bits of x + (x