算法优化及二进制位距
另一个可进行64位优化之处是在位串中计算（二进制）位距。二进制位距常用于进行分类与查找对象的相似之处的数据采集与AI（人工智能）程序，其通常表示为二进制描述符（位串）。此处优化的重点是位距算法，因为它会在系统中每对对象之间重复执行。
最知名的位距度量算法是加重平均位距，其是位中的一个最小数，并能被改变以转换为另一个位串。换句话来说，你可以使用XOR位运算符来结合位串，并利用得到的结果计算出位数。
如例7中采用了如上算法的程序，最明显的优化之处是去掉了临时位集，并同时计算XOR与总数量。而临时文件的产生是C++编译器的"内部运动"，且因为内存的复制与重分配，降低了程序效率，请看例8：
例7：
#include ＜bitset＞
using namespace std;
const unsigned BSIZE = 1000;
typedef bitset＜BSIZE＞ bset;
unsigned int humming_distance(const bset& set1, const bset& set2)
{
bset xor_result = set1 ^ set2;
return xor_result.count();
}
例8：
{
unsigned int hamming;
int a1[2048];
int a2[2048];
long long* pa1;
long long* pa2;
pa1 = (long long*) a1; pa2 = (long long*) a2;
hamming = 0;
for (int i = 0; i ＜ sizeof(a1) / sizeof(long long); ++i)
{
long long b;
b = pa1[i] ^ pa2[i];
b = (b & 0x5555555555555555LU) + (b ＞＞ 1 & 0x5555555555555555LU);
b = (b & 0x3333333333333333LU) + (b ＞＞ 2 & 0x3333333333333333LU);
b = b + (b ＞＞ 4) & 0x0F0F0F0F0F0F0F0FLU;
b = b + (b ＞＞ 8);
b = b + (b ＞＞ 16);
b = b + (b ＞＞ 32) & 0x0000007F;
hamming += b;
}
}
图3
为了进一步加深理解，来看一下Tversky Index：
TI = BITCOUNT(A & B) / [a*(BITCOUNT(A-B) + b*BITCOUNT(B-A) + BITCOUNT(A & B)]
公式中包含了三个操作，BITCOUNT_AND(A, B)、BITCOUNT_SUB(A, B)、BITCOUNT_SUB(B, A)。三个操作能被结合成一条流水线操作，见图4。这种技术改进了数据存储位置，更好的复用了CPU缓存，也意味着减少CPU延迟及提高程序性能，见例9：
例9：
{
double ti;
int a1[2048];
int a2[2048];
long long* pa1;
long long* pa2;
pa1 = (long long*) a1; pa2 = (long long*) a2;
ti = 0;
for (int i = 0; i ＜ sizeof(a1) / sizeof(long long); ++i)
{
long long b1, b2, b3;
b1 = pa1[i] & pa2[i];
b2 = pa1[i] & ~pa2[i];
b3 = pa2[i] & ~pa1[i];
b1 = popcount(b1);
b2 = popcount(b2);
b3 = popcount(b3);
ti += double(b1) / double(0.4 * b2 + 0.5 * b3 + b1);
}
}
图4
上述的大多数算法都能通过基于矢量的指令加以编码--如单指令多数据（SIMD）。带有SIMD功能的CPU含有特殊的扩展寄存器（64位或128位）或执行单元，能一次载入几个机器字，并对它们进行一些并行的操作。最流行的SIMD引擎是Intel的SSE；AMD的3DNow!；Motorola、Apple、IBM的AltiVec。SIMD寄存器与通用寄存器不同，它们不允许你执行诸如IF这样的流量控制操作，这也使SIMD编程更加困难。不难看出，基于SIMD代码的可移植性也是有限的。可是，一个并行的64位优化算法能在概念上很容易地被转换为一个128位的SIMD算法；请参见例10，其使用SSE2指令集实现了一个XOR算法，此处使用了Intel C++编译器的内部兼容性。
例10：
void bit_xor(unsigned* dst, const unsigned* src, unsigned block_size)
{
const __m128i* wrd_ptr = (__m128i*)src;
const __m128i* wrd_end = (__m128i*)(src + block_size);
__m128i* dst_ptr = (__m128i*)dst;
do
{
__m128i xmm1 = _mm_load_si128(wrd_ptr);
__m128i xmm2 = _mm_load_si128(dst_ptr);
__m128i xmm1 = _mm_xor_si128(xmm1, xmm2);
__mm_store_si128(dst_ptr, xmm1);
++dst_ptr;
++wrd_ptr;
} while (wrd_ptr ＜ wrd_end);
}
既然在64位上数值优化有这些好处，那你还等什么呢？
