Sweet Snippet 之统计二进制中 1 的个数

痛定思痛。 2022-11-20 09:43 149阅读 0赞

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

#### 简介 ####

二进制中1的个数是[汉明重量(Hamming Weight)][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?  
    ][How to count the number of set bits in a 32-bit integer_]

[Hamming Weight]: https://zh.wikipedia.org/wiki/%E6%B1%89%E6%98%8E%E9%87%8D%E9%87%8F
[popcnt]: https://www.felixcloutier.com/x86/popcnt
[How to count the number of set bits in a 32-bit integer_]: https://stackoverflow.com/questions/109023/how-to-count-the-number-of-set-bits-in-a-32-bit-integer