汉明权重(hamming weight) ----- 计算数据位中1的个数_综合

汉明重量是一串符号中非零符号的个数。因此它等同于同样长度的全零符号串的汉明距离(在信息论中，两个等长字符串之间的汉明距离,是两个字符串对应位置的不同字符的个数)。在最为常见的数据位符号串中，它是1的个数。

本文参考文章1 文章2

在wiki百科中给出，计算1的个数，目前来说最好的是按照树状进行相加（当然比遍历要快很多，遍历就相当于一棵极不平衡的数）
在这里插入图片描述
下面是variable-precision SWAR算法的实现：

uint32_ t swar (uint32_ t i) {//步骤1i = (i & 0x55555555) + ((i >> 1) & 0x55555555) ;//步骤2i = (i & 0x33333333) + ((i >> 2) & 0x33333333) ;//步骤3i = (i & 0x0F0F0FOF) + ((i >> 4) & 0x0F0F0F0F) ;//步骤4i = (i*(0x01010101) >> 24) ;return i;
}

整体思路就是：先将相邻2位的1的数量计算出来，结果存放在这2位。然后将相邻4位的结果相加，结果存放在这4位，将相邻8位的结果相加，结果存放在这8位。最后计算整体1的数量，记录在高8位，然后通过右移运算，将结果放到低8位，得到最终结果。
在这里插入图片描述

先使用一个简单的8bit的串，来描述这个算法的基本思想

前提
使用abcdefgh来代表一个8bit的2进制串，其中a,b,c,d,e,f,g,h属于集合{0,1}
那么算法求解的目标输出是out=a+b+c+d+e+f+g+h

m1 = 01 01 01 01
x = (x & m1 ) + ((x >> 2) & m1 )

x&m1 = 0b0d0f0h
(x>>2)&m1 = 0a0c0e0g

求和得到： $a+b]_2[c+d]_2[e+f]_2[g+h]_2$ ,这里 $x]_2$ 表示二进制数为2位， $x]_4$ 这种表示二进制数为4位。其值=x(x表示10进制的值)。并使用其来表示自身包含的1的个数。

m2 = 0011 0011
x = (x & m2 ) + ((x >> 4) & m2 )

x&m2 = 00 $c+d]_2$ 00 $g+h]_2$
(x>>4)&m2 = 00 $a+b]_2$ 00 $e+f]_2$
求和得到： $a+b+c+d]_4$ $e+f+g+h]_4$

m4 = 00001111
x = (x & m4 ) + ((x >> 4) & m4 )

x&m4 = 0000 $e+f+g+h]_4$
(x>>4)&m2 = 0000 $a+b+c+d]_4$
求和得到： $a+b+c+d+e+f+g+h]_8$

其十进制数表示的值就是问题的解，至此问题得解。

到这里可以很清楚的看到，算法是使用了分治的思想，每步将问题划分成子问题，然后合并来减小问题的规模。

求解问题的过程像是一棵倒置的二叉树。先将n位的二进制相邻的两位两两分为一组，并巧妙的利用移位和掩码来使其利用自身来表示所得到的和。

这样从宏观上来看，问题就被简化成规模为n/2bit(这里的bit其实已经是虚指了，其实理解为unit更好)的问题求解了，同样的，继续两两划分成一组分治求解。经过lg（n）步，得到最终的解。

由以上分析可见，算法的复杂度为O（lgn）。

对于popcount的逐渐改进方法如下：

typedef unsigned __int64 uint64; 
const uint64 m1 = 0x5555555555555555;
const uint64 m2 = 0x3333333333333333; 
const uint64 m4 = 0x0f0f0f0f0f0f0f0f;
const uint64 m8 = 0x00ff00ff00ff00ff;  
const uint64 m16 = 0x0000ffff0000ffff; 
const uint64 m32 = 0x00000000ffffffff; 
const uint64 hff = 0xffffffffffffffff; 
const uint64 h01 = 0x0101010101010101;//这个是上文介绍的朴素算法
int popcount_1(uint64 x) {x = (x & m1 ) + ((x >>  1) & m1 ); x = (x & m2 ) + ((x >>  2) & m2 ); x = (x & m4 ) + ((x >>  4) & m4 ); x = (x & m8 ) + ((x >>  8) & m8 ); x = (x & m16) + ((x >> 16) & m16); x = (x & m32) + ((x >> 32) & m32); return x;
}//这里基于了这样一个事实:ab-0a得到的值为ab中1的个数。
//简单证明：若a为0，那么0a=0,减0无变化，那么b就是结果。
//若a位1，那么只有两种情况，10-01 = 01, 11-01 = 10.都符合上述事实。
//这样x -= (x >> 1) & m1和 x = (x & m1 ) + ((x >> 1) & m1 )的结果相同，却节省了1个操作。int popcount_2(uint64 x) {x -= (x >> 1) & m1;             x = (x & m2) + ((x >> 2) & m2); x = (x + (x >> 4)) & m4;        x += x >>  8;  x += x >> 16;  x += x >> 32;  return x &0xff;
}//在最后一步返回时做了改进
int popcount_3(uint64 x) {x -= (x >> 1) & m1;             x = (x & m2) + ((x >> 2) & m2); x = (x + (x >> 4)) & m4;        return (x * h01)>>56;  //returns left 8 bits of x + (x<<8) + (x<<16) + (x<<24) + ... 
}//在二进制表示中，数字 n中最低位的 1 总是对应 n - 1 中的 0 。因此，将 n 和 n - 1 进行与运算总是能把 n 中最低位的 1 变成 0，并保持其他位不变。int popcount_4(uint64 x) {uint64 count;for (count=0; x; count++)x &= x-1;return count;
}//最有趣的是查表法，当有足够的内存时，我们可以用空间换时间，从而得到O(1)的最优算法。
#define f(y) if ((x &= x-1) == 0) return y;
int popcount_5(uint64 x) {if (x == 0) return 0;f( 1) f( 2) f( 3) f( 4) f( 5) f( 6) f( 7) f( 8)f( 9) f(10) f(11) f(12) f(13) f(14) f(15) f(16)f(17) f(18) f(19) f(20) f(21) f(22) f(23) f(24)f(25) f(26) f(27) f(28) f(29) f(30) f(31) f(32)f(33) f(34) f(35) f(36) f(37) f(38) f(39) f(40)f(41) f(42) f(43) f(44) f(45) f(46) f(47) f(48)f(49) f(50) f(51) f(52) f(53) f(54) f(55) f(56)f(57) f(58) f(59) f(60) f(61) f(62) f(63)return 64;
}
#define f(y) if ((x |= x+1) == hff) return 64-y;

将此算法应用到leetcode191 和 leetcode338

leetcode191就使用popcount4的解法

class Solution {
public:int hammingWeight(uint32_t n) {int count = 0;while( n ){count ++;n &= n-1;}return count;}
};

leetcode338 也是popcount4来求解

class Solution {private:int popcount(uint32_t n) {int count = 0;while( n ){count ++;n &= n-1;}return count;}public:vector<int> countBits(int num) {vector<int> res( num+1, 0 );for( int i = 1; i <= num; i ++ )res[i] = popcount(i);return res;}
};