计算字节数组中1比特数量的最快方法：除查表法外还有哪些可靠方案？

你当前使用的查表法已经是非常高效的方案之一，尤其在处理单字节数据时，查表能通过O(1)索引直接得到结果，循环累加的开销极低。不过确实存在几种被广泛认可的优化方案，具体选择取决于硬件环境、数据规模和编译器优化能力：

1. 硬件指令集加速 #

现代CPU都提供了专门的位计数指令，比如x86架构的POPCNT（Population Count）指令，ARM架构的VCNT或CNT指令。这类指令能直接对多字节数据（如32位/64位整数）进行位计数，效率远高于查表法——一次指令就能处理多个字节，大幅减少循环次数。

在C++中可通过编译器内置函数调用这些指令，示例代码如下：

#include <cstdint>

constexpr size_t nbytes = 256;
std::array<uint8_t, nbytes> bytes;

size_t count1() {
    size_t res = 0;
    // 按64位块批量处理，降低循环次数
    size_t num_64bit = nbytes / sizeof(uint64_t);
    uint64_t* ptr_64 = reinterpret_cast<uint64_t*>(bytes.data());
    for (size_t i = 0; i < num_64bit; ++i) {
        res += __builtin_popcountll(ptr_64[i]); // GCC/Clang 64位popcount
        // 若使用MSVC，替换为__popcnt64
    }
    // 处理剩余的不足64位的字节
    size_t remaining = nbytes % sizeof(uint64_t);
    uint8_t* ptr_8 = reinterpret_cast<uint8_t*>(ptr_64 + num_64bit);
    for (size_t i = 0; i < remaining; ++i) {
        res += __builtin_popcount(ptr_8[i]);
    }
    return res;
}

这种方法的核心是利用硬件原生指令，在大数据组场景下优势尤为明显。

2. 位运算分治法（纯软件实现） #

如果需要兼容不支持硬件位计数指令的老旧CPU，可采用经典的位运算分治法，完全通过位操作完成位计数，无需查表：

uint32_t count_bits(uint32_t x) {
    x = x - ((x >> 1) & 0x55555555);
    x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
    x = (x + (x >> 4)) & 0x0F0F0F0F;
    x = x + (x >> 8);
    x = x + (x >> 16);
    return x & 0x0000003F;
}

该方案无需额外内存存储查表，但效率通常低于查表法或硬件指令，适合无硬件指令支持的场景。

3. SIMD并行处理 #

针对超大规模字节数组，可使用SIMD（单指令多数据）指令，比如x86的SSE/AVX、ARM的NEON，一次并行处理16/32个字节的位计数。这种方法在处理GB级数据时效率极高，但代码复杂度较高，需针对不同指令集编写适配代码。

关于“始终最快”的说明 #

不存在绝对始终最快的方案，效率取决于以下因素：

• 硬件平台：支持POPCNT/SIMD的CPU更适配硬件指令方案；老旧CPU可能更适合查表法或位运算
• 数据规模：小数组场景下，查表法的开销可能低于硬件指令；大数据组下，硬件指令或SIMD的优势更显著
• 编译器优化：优秀的编译器可能自动将查表法或位运算代码优化为硬件指令调用

如果是通用平台场景，优先推荐使用编译器内置的popcount函数——编译器会根据目标平台自动选择最优实现（支持POPCNT则生成硬件指令，不支持则 fallback 到软件实现）。而查表法在嵌入式系统或无法依赖编译器优化的场景中依然是可靠选择。

内容的提问来源于stack exchange，提问作者Zeyu Zhang CN