想求汉明距离，如何提高效率
想求汉明距离，怎么提高效率
有一串0，1二进制码保存在向量或数组中，如数组a[0]=1, a[1]=1, a[2]=1,……a[255]=0, b[0]=1, b[1]=0,……,b[255]=0，现在要比较a、b这两个二进制串的汉明距离，由于这样二进制串太多，如果直接用for循环来判断每个数是否相同来求汉明距离的效率太低，有什么好办法吗？比如可不可以几位二进制合并一个数，或转化为其他类型的来计算？
------解决思路----------------------
http://blog.csdn.net/fengzhizizhizizhizi/article/details/21404383
------解决思路----------------------
测试代码：
编译需要ms VC++ 2010或者intel C++ 11.1，这些都是5、6年前的版本了，要求并不高（intel C++ composer XE 2011的编译器版本是13.0，XE 2013是14.0，XE 2015是15.0）。gcc其实也支持intrinsics，不过它的助记符采用自己的一套东西，我没那么多时间去适应它。
上面的代码之所以在__m256i和__m256d之间强制类型转换，是因为没有使用_mm256_xor_si256（对应vpxor指令），后者需要AVX2才能支持，对编译器的要求也高一些，要VC++ 2013或者intel C++ XE 2011 update 7。
支持AVX的处理器2011年就出了，intel SNB或者AMD Bulldozer档次的就可以（话说AMD真是蓝翔技校的好合作伙伴，推土机、打桩机、挖掘机一样都不少），目前很普遍了。
可以在程序启动时检测一下AVX是否可以用，如果不可用则使用常规版本的函数。检测AVX的代码网上很多，无非就是检查CPUID返回的一些标志位。
有一串0，1二进制码保存在向量或数组中，如数组a[0]=1, a[1]=1, a[2]=1,……a[255]=0, b[0]=1, b[1]=0,……,b[255]=0，现在要比较a、b这两个二进制串的汉明距离，由于这样二进制串太多，如果直接用for循环来判断每个数是否相同来求汉明距离的效率太低，有什么好办法吗？比如可不可以几位二进制合并一个数，或转化为其他类型的来计算？
------解决思路----------------------
http://blog.csdn.net/fengzhizizhizizhizi/article/details/21404383
------解决思路----------------------
测试代码：
#include <intrin.h>
// sample data
__declspec(align(32)) __m256i X = {0, 0, 0, 0, 0, 0, 0, 1};
__declspec(align(32)) __m256i Y = {2, 0, 0, 0, 0, 0, 0, 3};
int HammingDistance256_intrinsic(__m256i &a, __m256i &b)
{
__m256i c = *(__m256i *)&_mm256_xor_pd(*(__m256d *)&a, *(__m256d *)&b);
/* for 64-bit only
return _mm_popcnt_u64(c.m256i_u64[0]) +
_mm_popcnt_u64(c.m256i_u64[1]) +
_mm_popcnt_u64(c.m256i_u64[2]) +
_mm_popcnt_u64(c.m256i_u64[3]);
*/
return _mm_popcnt_u32(c.m256i_u32[0]) +
_mm_popcnt_u32(c.m256i_u32[1]) +
_mm_popcnt_u32(c.m256i_u32[2]) +
_mm_popcnt_u32(c.m256i_u32[3]) +
_mm_popcnt_u32(c.m256i_u32[4]) +
_mm_popcnt_u32(c.m256i_u32[5]) +
_mm_popcnt_u32(c.m256i_u32[6]) +
_mm_popcnt_u32(c.m256i_u32[7]);
}
// usage
printf("%d\n", HammingDistance256_intrinsic(X, Y)); // result is 2
编译需要ms VC++ 2010或者intel C++ 11.1，这些都是5、6年前的版本了，要求并不高（intel C++ composer XE 2011的编译器版本是13.0，XE 2013是14.0，XE 2015是15.0）。gcc其实也支持intrinsics，不过它的助记符采用自己的一套东西，我没那么多时间去适应它。
上面的代码之所以在__m256i和__m256d之间强制类型转换，是因为没有使用_mm256_xor_si256（对应vpxor指令），后者需要AVX2才能支持，对编译器的要求也高一些，要VC++ 2013或者intel C++ XE 2011 update 7。
支持AVX的处理器2011年就出了，intel SNB或者AMD Bulldozer档次的就可以（话说AMD真是蓝翔技校的好合作伙伴，推土机、打桩机、挖掘机一样都不少），目前很普遍了。
可以在程序启动时检测一下AVX是否可以用，如果不可用则使用常规版本的函数。检测AVX的代码网上很多，无非就是检查CPUID返回的一些标志位。