[科普中國]-漢明重量

漢明重量是一串符號中非零符號的個數(shù)。因此它等同于同樣長度的全零符號串的漢明距離。在最為常見的數(shù)據(jù)位符號串中，它是1的個數(shù)。

漢明重量是以理查德·衛(wèi)斯里·漢明的名字命名的，它在包括信息論、編碼理論、密碼學(xué)等多個領(lǐng)域都有應(yīng)用。1

SWAR算法“計算漢明重量”第一步：
計算出來的值i的二進制可以按每2個二進制位為一組進行分組，各組的十進制表示的就是該組的漢明重量。

第二步：
計算出來的值i的二進制可以按每4個二進制位為一組進行分組，各組的十進制表示的就是該組的漢明重量。

第三步：
計算出來的值i的二進制可以按每8個二進制位為一組進行分組，各組的十進制表示的就是該組的漢明重量。

第四步：
i * (0x01010101)計算出漢明重量并記錄在二進制的高八位，>>24語句則通過右移運算，將漢明重量移到最低八位，最后二進制對應(yīng)的的十進制數(shù)就是漢明重量。

算法時間復(fù)雜度是O（1）的。

相關(guān)代碼

// 計算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}實現(xiàn)在密碼學(xué)以及其它應(yīng)用中經(jīng)常需要計算數(shù)據(jù)位中1的個數(shù)，針對如何高效地實現(xiàn)人們已經(jīng)廣泛地進行了研究。一些處理器使用單個的命令進行計算，另外一些根據(jù)數(shù)據(jù)位向量使用并行運算進行處理。對于沒有這些特性的處理器來說，已知的最好解決辦法是按照樹狀進行相加。例如，要計算二進制數(shù)A=0110110010111010中1的個數(shù)，這些運算可以表示為圖一：

這里的運算是用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