位计数算法
在位集算法中最重要的一个操作是在位串中计算1位的数量，默认的操作方法是把每一个整数分成4个字符，并在一张预先计算好的位计数表中依次查找。这种线性操作的方法能用一种16位宽的表格加以改进，所付出的代价是表格可能要更大才行。此外，更大的表格很可能会产生一些额外的内存取数操作，由此影响CPU缓存命中率，结果并没有带来想象中的性能提升。
作为另一个可供选择的方法，例4就没有使用查找表，但却一次并行计算两个int。
例4：
int popcount(long long b)
{
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;
return (int) b;
}
位串词典比较
可进行64位优化的另一种程序是位集中的词典比较，其最直接的实现是每次从位序列中取出两个字，并一位一位地转换进行比较，此迭代算法具有O(N/2)的复杂度，此处的N是总的位数。例5中演示了两个字的迭代比较法；此算法并不能通过64位并行化处理极大地提高性能。然而，例6演示了另一种可供选择的算法，其复杂性与机器字（不是位）数除以2成正比，其在64位上极具潜力。
例5：
int bitcmp(int w1, int w2)
{
while (w1 != w2)
{
int res = (w1 & 1) - (w2 & 1);
if (res != 0)
return res;
w1 ＞＞= 1;
w2 ＞＞= 1;
}
return 0;
}
例6：
int compare_bit_string(int a1[2048], int a2[2048])
{
long long* pa1 = (long long*) a1;
long long* pa2 = (long long*) a2;
for (int i = 0; i ＜ sizeof(a1) / sizeof(long long); ++i)
{
long long w1, w2, diff;
w1 = a1[i];
w2 = a2[i];
diff = w1 ^ w2;
if (diff)
{
return (w1 & diff & -diff) ? 1 : -1;
}
}
return 0;
}
面临的问题
问题来了，为了64位，我们犯得着这样吗？当代的32位CPU都是超标量、推理性执行机器，具有在几个执行区域中并行乱序地同时执行几条指令的能力，而不需要程序员的干预；反观64位处理器只展示了其具有同样的性能--但只是在纯64位中；话说回来，在如Intel Itanium（安腾处理器）特别强调并行编程的某些架构上，并且在编译器级别显式地进行了优化的情况下，程序代码适合于64位，并且已为64位优化就显得尤为必要。
还有一点，程序的性能不只是受限于CPU的MHz表现，而且也受限于CPU的内存带宽--其又受限于系统总线，总之，上述的算法不可能总是表现出最高性能，这也是不可改变的一个事实，并且硬件设计师也非常了解。当然，我们也看到了双通道内存控制器所带来的效率上的提高，并且内存速度也在稳步向前发展，这在一定程度上减轻了系统总线成为瓶颈的可能性，面对当今发展越来越快的硬件，经过优化的64位算法将会有更好的表现。
