更新：请阅读代码，这与计算一个 int 中的位无关
是否可以使用一些聪明的汇编程序来提高以下代码的性能？
uint bit_counter[64];
void Count(uint64 bits) {
bit_counter[0] += (bits >> 0) & 1;
bit_counter[1] += (bits >> 1) & 1;
// ..
bit_counter[63] += (bits >> 63) & 1;
}
Count在我算法的最内层循环中。
更新： 架构：x86-64、Sandy Bridge，因此可以使用 SSE4.2、AVX1 和旧技术，但不能使用 AVX2 或 BMI1/2。
bits变量几乎具有随机位（接近半个零和半个）
您可以尝试使用 SSE 执行此操作，每次迭代增加 4 个元素。
警告：未经测试的代码如下...
#include <stdint.h>
#include <emmintrin.h>
uint32_t bit_counter[64] __attribute__ ((aligned(16)));
// make sure bit_counter array is 16 byte aligned for SSE
void Count_SSE(uint64 bits)
{
const __m128i inc_table[16] = {
_mm_set_epi32(0, 0, 0, 0),
_mm_set_epi32(0, 0, 0, 1),
_mm_set_epi32(0, 0, 1, 0),
_mm_set_epi32(0, 0, 1, 1),
_mm_set_epi32(0, 1, 0, 0),
_mm_set_epi32(0, 1, 0, 1),
_mm_set_epi32(0, 1, 1, 0),
_mm_set_epi32(0, 1, 1, 1),
_mm_set_epi32(1, 0, 0, 0),
_mm_set_epi32(1, 0, 0, 1),
_mm_set_epi32(1, 0, 1, 0),
_mm_set_epi32(1, 0, 1, 1),
_mm_set_epi32(1, 1, 0, 0),
_mm_set_epi32(1, 1, 0, 1),
_mm_set_epi32(1, 1, 1, 0),
_mm_set_epi32(1, 1, 1, 1)
};
for (int i = 0; i < 64; i += 4)
{
__m128i vbit_counter = _mm_load_si128(&bit_counter[i]);
// load 4 ints from bit_counter
int index = (bits >> i) & 15; // get next 4 bits
__m128i vinc = inc_table[index]; // look up 4 increments from LUT
vbit_counter = _mm_add_epi32(vbit_counter, vinc);
// increment 4 elements of bit_counter
_mm_store_si128(&bit_counter[i], vbit_counter);
} // store 4 updated ints
}
它是如何工作的：基本上我们在这里所做的只是对原始循环进行矢量化，以便我们每次循环迭代处理 4 位而不是 1。所以我们现在有 16 次循环迭代而不是 64 次。对于每次迭代，我们从 加载 4 位bits，然后使用它们作为 LUT 的索引，其中包含当前 4 位的 4 个增量的所有可能组合。然后我们将这 4 个增量添加到 bit_counter 的当前 4 个元素中。
加载、存储和添加的数量减少了 4 倍，但这将在某种程度上被 LUT 加载和其他内务处理所抵消。不过，您可能仍会看到 2 倍的速度提升。如果您决定尝试一下，我很想知道结果。
也许你可以一次做 8 个，通过 8 位间隔 8 并保持 8 个 uint64 的计数。count不过，每个单个计数器只有 1 个字节，因此在您必须解压缩这些 uint64 之前，您只能累积 255 次调用。
编辑至于“位位置桶累积”（bit_counter[]），我觉得这可能是 valarrays + 掩码的好案例。不过，那将是相当多的编码+测试+分析。让我知道你是否真的感兴趣。
这些天来，您可以非常接近使用绑定元组（TR1、boost 或 C++11）的 valarray 行为；我有一种感觉，它会变得更容易阅读和更慢编译。
显然，这可以通过“垂直计数器”快速完成。来自@steike的 Bit tricks ( archive )现已失效的页面：
考虑一个普通的整数数组，我们在其中水平读取位：
msb<-->lsb x[0] 00000010 = 2 x[1] 00000001 = 1 x[2] 00000101 = 5顾名思义，垂直计数器垂直存储数字；也就是说，一个 k 位计数器存储在 k 个字中，每个字中有一个位。
x[0] 00000110 lsb ↑ x[1] 00000001 | x[2] 00000100 | x[3] 00000000 | x[4] 00000000 msb ↓ 512使用这样存储的数字，我们可以使用按位运算一次递增它们的任何子集。
我们在对应于我们要递增的计数器的位置创建一个位图，并从 LSB 向上循环遍历数组，随时更新位。一次加法的“进位”成为数组下一个元素的输入。
input sum -------------------------------------------------------------------------------- A B C S 0 0 0 0 0 1 0 1 sum = a ^ b 1 0 0 1 carry = a & b 1 1 1 1 carry = input; long *p = buffer; while (carry) { a = *p; b = carry; *p++ = a ^ b; carry = a & b; }对于 64 位字，循环平均运行 6-7 次——迭代次数由最长的进位链决定。
你可以像这样展开你的函数。它可能比您的编译器可以做的更快！
// rax as 64 bit input
xor rcx, rcx //clear addent
add rax, rax //Copy 63th bit to carry flag
adc dword ptr [@bit_counter + 63 * 4], ecx //Add carry bit to counter[64]
add rax, rax //Copy 62th bit to carry flag
adc dword ptr [@bit_counter + 62 * 4], ecx //Add carry bit to counter[63]
add rax, rax //Copy 62th bit to carry flag
adc dword ptr [@bit_counter + 61 * 4], ecx //Add carry bit to counter[62]
// ...
add rax, rax //Copy 1th bit to carry flag
adc dword ptr [@bit_counter + 1 * 4], ecx //Add carry bit to counter[1]
add rax, rax //Copy 0th bit to carry flag
adc dword ptr [@bit_counter], ecx //Add carry bit to counter[0]
编辑：
您也可以尝试使用双倍增量，如下所示：
// rax as 64 bit input
xor rcx, rcx //clear addent
//
add rax, rax //Copy 63th bit to carry flag
rcl rcx, 33 //Mov carry to 32th bit as 0bit of second uint
add rax, rax //Copy 62th bit to carry flag
adc qword ptr [@bit_counter + 62 * 8], rcx //Add rcx to 63th and 62th counters
add rax, rax //Copy 61th bit to carry flag
rcl rcx, 33 //Mov carry to 32th bit as 0bit of second uint
add rax, rax //Copy 60th bit to carry flag
adc qword ptr [@bit_counter + 60 * 8], rcx //Add rcx to 61th and 60th counters
//...
您可以使用一组不同大小的计数器。首先在 2 位计数器中累积 3 个值，然后将它们解包并更新 4 位计数器。当 15 个值准备好时，解包到字节大小的计数器，并在 255 个值后更新 bit_counter[]。
所有这些工作都可以在 128 位 SSE 寄存器中并行完成。在现代处理器上，只需一条指令即可将 1 位解压缩为 2。只需使用 PCLMULQDQ 指令将源四字乘以自身。这将使源位与零交错。同样的技巧可能有助于将 2 位解包为 4。4 位和 8 位的解包可以通过混洗、解包和简单的逻辑运算来完成。
平均性能似乎不错，但是额外的计数器和相当多的汇编代码的价格是 120 字节。
如果您计算每个半字节（16 种可能性）在每个偏移量（16 种可能性）处出现的频率，您可以轻松地总结结果。而这 256 个总和很容易保存：
unsigned long nibble_count[16][16]; // E.g. 0x000700B0 corresponds to [4][7] and [2][B]
unsigned long bitcount[64];
void CountNibbles(uint64 bits) {
// Count nibbles
for (int i = 0; i != 16; ++i) {
nibble_count[i][bits&0xf]++;
bits >>= 4;
}
}
void SumNibbles() {
for (int i = 0; i != 16; ++i) {
for (int nibble = 0; nibble != 16; ++nibble) {
for(int bitpos = 0; bitpos != 3; ++bitpos) {
if (nibble & (1<<bitpos)) {
bitcount[i*4 + bitpos] += nibble_count[i][nibble];
}
}
}
}
}
一般来说，没有办法回答这个问题。这一切都取决于编译器和底层架构。唯一真正了解的方法是尝试不同的解决方案并进行测量。（例如，在某些机器上，轮班可能非常昂贵。在其他机器上，不会。）对于初学者，我会使用类似的东西：
uint64_t mask = 1;
int index = 0;
while ( mask != 0 ) {
if ( (bits & mask) != 0 ) {
++ bit_counter[index];
}
++ index;
mask <<= 1;
}
完全展开循环可能会提高性能。根据架构，将其替换为if：
bit_counter[index] += ((bits & mask) != 0);
可能会更好。或者更糟……不可能提前知道。也有可能在某些机器上，系统地转移到低位并掩蔽，就像你正在做的那样，将是最好的。
一些优化还取决于典型数据的样子。如果大多数字只设置了一个或两个位，您可能会通过一次测试一个字节或一次测试四个位并完全跳过全为零的那些来获得收益。
这是相当快的：
void count(uint_fast64_t bits){
uint_fast64_t i64=ffs64(bits);
while(i64){
bit_counter[i64-1]++;
bits=bits & 0xFFFFFFFFFFFFFFFF << i64;
i64=ffs64(bits);
}
}
您需要快速实现 64 位的ffs。对于大多数编译器和 CPU，这是一条指令。循环对字中的每个位执行一次，因此bits=0会非常快，而 64 位的位1会更慢。
我在 64 位 Ubuntu 下使用 GCC 进行了测试，它产生的数据输出与您的相同：
void Count(uint64 bits) {
bit_counter[0] += (bits >> 0) & 1;
bit_counter[1] += (bits >> 1) & 1;
// ..
bit_counter[63] += (bits >> 63) & 1;
}
速度根据164 位字中的位数而变化。