如何实现64位整数的1比特位计数算法？

针对64位整数统计其中1比特位的数量，常用的高效方案有以下几种：

1. 分治法（汉明重量经典实现） #

这是固定时间复杂度的高效算法，通过分阶段计算相邻比特位的和，逐步压缩数据规模，最终得到总数量。代码实现如下：

uint64_t bit_count(uint64_t n) {
    // 计算每2位中1的数量
    n = (n & 0x5555555555555555) + ((n >> 1) & 0x5555555555555555);
    // 计算每4位中1的数量
    n = (n & 0x3333333333333333) + ((n >> 2) & 0x3333333333333333);
    // 计算每8位中1的数量
    n = (n & 0x0F0F0F0F0F0F0F0F) + ((n >> 4) & 0x0F0F0F0F0F0F0F0F);
    // 计算每16位中1的数量
    n = (n & 0x00FF00FF00FF00FF) + ((n >> 8) & 0x00FF00FF00FF00FF);
    // 计算每32位中1的数量
    n = (n & 0x0000FFFF0000FFFF) + ((n >> 16) & 0x0000FFFF0000FFFF);
    // 计算64位中1的总数量
    n = (n & 0x00000000FFFFFFFF) + ((n >> 32) & 0x00000000FFFFFFFF);
    return n;
}

该算法时间复杂度为O(1)，仅需固定次数的位运算，完全适配64位整数场景。

2. 布莱恩·克尼根算法 #

通过不断清除整数的最低位1，统计清除操作的次数：

uint64_t bit_count(uint64_t n) {
    uint64_t count = 0;
    while (n) {
        n &= n - 1; // 清除最低位的1
        count++;
    }
    return count;
}

该算法时间复杂度为O(k)，其中k是整数中1的个数，当1的数量较少时，效率优于分治法。

3. 硬件指令调用 #

现代编译器大多提供内置函数直接调用CPU的汉明重量计算指令，效率最高：

// GCC/Clang 环境
uint64_t bit_count(uint64_t n) {
    return __builtin_popcountll(n);
}

// MSVC 环境
uint64_t bit_count(uint64_t n) {
    return __popcnt64(n);
}

如果目标平台支持相关硬件指令，这是性能最优的选择。

针对你给出的测试用例0x123456789abcdef0，上述三种算法都能正确返回32。

内容的提问来源于stack exchange，提问作者Software Guy