本文简述了几种用于统计二进制中 1 的个数的方法

二进制中1的个数是汉明重量(Hamming Weight)的一种,广泛应用于二进制比较等操作中,举例来说,二进制 1011 的汉明重量便是 3,因为该二进制中总共包含 3 个 1.

最简单的实现方法便是遍历二进制的各个位,然后统计各个位中 1 的个数,代码实现的话大概是这个样子(Lua 代码(5.4),下同):

function count_1_raw(val)
    local count = 0
    
    while val > 0 do
        if (val & 1) == 1 then
            count = count + 1
        end
        val = val >> 1
    end
    
    return count
end

如果二进制范围比较有限的话,我们完全可以采用(预计算)缓存的方法来实现个数统计,而对于二进制范围比较大的情况,缓存实现也可作为整体实现的一个(补充)分支:

-- support 4 bits
local count_1_buffer_table = 
{
    [0] = 0,
    [1] = 1,
    [2] = 1,
    [3] = 2,
    [4] = 1,
    [5] = 2,
    [6] = 2,
    [7] = 3,
    [8] = 1,
    [9] = 2,
    [10] = 2,
    [11] = 3,
    [12] = 2,
    [13] = 3,
    [14] = 3,
    [15] = 4,
}

function count_1_buffer(val)
    return count_1_buffer_table[val]
end

• variable-precision SWAR

variable-precision SWAR 是一种"分组"统计二进制中 1 的个数的方法,说的有些抽象,我们先看代码(用于 32 位二进制数):

function count_1_swar(val)
    val = (val & 0x55555555) + ((val >> 1) & 0x55555555)
    val = (val & 0x33333333) + ((val >> 2) & 0x33333333)
    val = (val & 0x0F0F0F0F) + ((val >> 4) & 0x0F0F0F0F)
    val = (val * 0x01010101) >> 24
    return val
end

一眼望去似乎不知所云,我们分解来看:

0x55555555 的二进制表示为 01010101010101010101010101010101,很容易看出该二进制是以 2 位(“01”)为一组的,通过代码:

val = (val & 0x55555555) + ((val >> 1) & 0x55555555)

我们可以让 val 中每 2 位一组的二进制变更为之前该 2 位二进制中 1 的个数(譬如 11 会变更为 10(10 即是 2,表示 11 中 1 的个数为 2))

理解了第一步,后面二步也便可以理解了,因为思路其实是一样的,只是分组位数逐步提高(2位一组 -> 4位一组 -> 8 位一组):

val = (val & 0x33333333) + ((val >> 2) & 0x33333333)
val = (val & 0x0F0F0F0F) + ((val >> 4) & 0x0F0F0F0F)

经过了上面的三步, val 以 8 位一组的方式记录了原二进制中对应 8 位二进制的 1 的个数,通过乘以常数 0x01010101,我们可以将这 4 个 8 位二进制(总共 32 位)在乘积的前8位中进行累加,由于累加发生在前8位,我们最后需要右移 24 位来获取最终的结果:

val = (val * 0x01010101) >> 24

有一些指令集内建支持计算汉明重量(譬如 x86 的 popcnt),直接使用这些指令来统计二进制中 1 的个数应该是最快的.

• How to count the number of set bits in a 32-bit integer?