Sweet Snippet 之 统计二进制中 1 的个数
Sweet Snippet 之 统计二进制中 1 的个数
本文简述了几种用于统计二进制中 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 的个数应该是最快的.