[db:标题]
摘要：介绍了在不同指令集环境下(SSE4SSE3SSE2)统计二进制中1的个数的优化，其优化速度较最原始版本的有近80倍提高。
关于这个问题，网络上讨论的很多，可以找到大量的资料，我觉得就就是下面这一篇讲的最好,也非常的全面：
统计无符号整数二进制中 1 的个数（Hamming Weight）
在指令集不参与的情况下，分治法速度最快，MIT HAKMEM 169 算法因为最后有一个mod取余操作，速度要稍微慢一点，256元素的查表算法速度要次之，当然，其实要建议那个256元素的表不要使用int类型，而是使用unsigned char类型的，尽量减少表的内存占用量，也意味着cache miss小一些。 16位的查表算法速度反而慢了不少，主要是因为他用while，即使我们把他展开，也需要8次数据组合，还是比16位的慢。其他的就不要说了，都比较慢。
在SSE4指令集能得到CPU的支持时，可以有一个直接的指令_mm_popcnt_u32可以使用，这个就可以加速很多了，一个常用的过程如下：
Amount = 0;
for (int Y = 0; Y < Length; Y++)
{
Amount += _mm_popcnt_u32(Array[Y]);
}
一千万的随机数据，用这个指令大概只要3.2毫秒多就可以处理完成，如果稍微改下代码，让他能并行化一点，如下所示：
Amount = 0;
for (int Y = 0; Y < Length; Y+=4)
{
int T0 = _mm_popcnt_u32(Array[Y + 0]);
int T1 = _mm_popcnt_u32(Array[Y + 1]);
int T2 = _mm_popcnt_u32(Array[Y + 2]);
int T3 = _mm_popcnt_u32(Array[Y + 3]);
Amount += T0 + T1 + T2 + T3;
}
还可以提高到大约2.7ms就可以处理完。
其实，现在在运行的新的CPU基本上没有那个不支持SSE4的了，但是也不排除还有一些老爷机。因为SSE4最早是2008年发布的，如果CPU不支持SSE4，但是支持SSE3(2004年发布的），那是否有合适的指令集能加速这个过程呢，实际上也是有的。
我们这里喵上了统计无符号整数二进制中 1 的个数（Hamming Weight）一文中的16元素查表算法，原文中的代码为：
Amount = 0;
for (int Y = 0; Y < Length; Y++)
{
unsigned int Value = Array[Y];
while (Value)
{
Amount += Table16[Value & 0xf];
Value >>= 4;
}
}
这个明显是不合适指令处理的，前面说了，这个可以展开，展开后形式如下：
Amount = 0;
for (int Y = 0; Y < Length; Y++)
{
unsigned int Value = Array[Y];
Amount += Table16[Value & 0xf] + Table16[(Value >> 4) & 0xf] + Table16[(Value >> 8) & 0xf] + Table16[(Value >> 12) & 0xf] +
Table16[(Value >> 16) & 0xf] + Table16[(Value >> 20) & 0xf] + Table16[(Value >> 24) & 0xf] + Table16[(Value >> 28) & 0xf];
}
仔细观察他的意思就是提取内存的4位，然后根据4位的值来查16个元素的表，我在之前的多个文章里都有提高，16个元素的表（表内的值不能超过255）是可以借用一个_mm_shuffle_epi8指令进行优化的，一次性得到16个值。
_mm_shuffle_epi8是在SSE3就开始支持的，因此，这一改动可以将硬件的适应性提前4年。