最近一个需求需要使用golang实现一个兼容redis的无压缩的bitmap,需要提供一个bitcoun函数来统计这个bitmap中二进制位1的个数,查了一圈并没有找到类似的第三方库,因此决定自己实现一个.(利用一切机会造轮子
1. 问题简化
问题本质实际就是给定一个数字,比如一个二进制数10101101
,计算出这个数字中二进制位1的个数,对于10101101
这个数字来说它有5个位为1,即:10101101
对于这个问题,最简单的办法就是挨位数,不过这个办法太笨了,没有逼格。
那么有没有银弹呢?答案是肯定的,而且还不止一种。
2. 查表法
对于一个8位的数字来说,它只有256个值,因此完全可以预先计算好每个值的二进制位1个个数写入到映射表中,使用时直接查询这张映射表即可。
伪代码如下所示:
var count1map = map[uint8]uint8 {
0b0000_0000: 0,
0b0000_0001: 1,
...
0b1111_1111: 8,
}
func bitcount(x uint8) uint8 {
return count1map[x]
}
3. 移位法
查表法虽然可以应对8位这样值数量有限的数字,但是对于uint64
or int64
这样64位的数字来说,它的值数量是非常多的,我们无法在内存中维护这样巨大的映射表,因此不能使用查表法来解决
Golang在bits
包中提供一个OnesCount64(x uint64) int
的函数,可以计算一个64位数字中二进制为1的个数,其源码如下:
const m0 = 0x5555555555555555 // 01010101 ...
const m1 = 0x3333333333333333 // 00110011 ...
const m2 = 0x0f0f0f0f0f0f0f0f // 00001111 ...
const m3 = 0x00ff00ff00ff00ff // etc.
const m4 = 0x0000ffff0000ffff
func OnesCount64(x uint64) int {
const m = 1<<64 - 1
x = x>>1&(m0&m) + x&(m0&m)
x = x>>2&(m1&m) + x&(m1&m)
x = (x>>4 + x) & (m2 & m)
x += x >> 8
x += x >> 16
x += x >> 32
return int(x) & (1<<7 - 1)
}
初看起来是有点懵逼的,一顿位运算操作怎么就能把1的个数算出来了呢?
这段代码注释中标明其来源于Hacker’s Delight第5章
别着急,我们还是采用自底向上的思想来拆解下。
3.1 2位数字二进制位1的个数
我们先想一下如何计算2位的数字二进制位1的个数,答案是非常简单的:
func OnesCount2(x uint2) int {
return (x & 0b01) + ((x >> 1) & 0b01)
}
x & 0b01
就是求第0位是不是1,((x >> 1) & 0b01)
就是求第1位是不是1,加起来就是x
这个2位数字二进制位1的个数。
3.2 4位数字二进制位1的个数
对于一个4位数字,如1011
,我们先按照3.1中的算法分别求出第3位与第2位即10
和 第1位与第0位即11
的二进制位1的个数,然后再加起来就得出这个4位数字的二进制位1的个数了。
伪代码如下所示:
func OnesCount4(x uint4) int {
x = x & 0b0101 + x >> 1 & 0b0101
return x & 0b0011 + x >> 2 & 0b0011
}
计算过程如图:
3.3 8位数字二进制位1的个数
8位数字计算过程与4位计算过程本质是相同的,都是拆解组合,伪代码如下:
func OnesCount8(x uint8) int {
x = x & 0b01010101 + x >> 1 & 0b01010101
x = x & 0b00110011 + x >> 2 & 0b00110011
return x & 0b00001111 + x >> 4 && 0b00001111
}
计算过程如下:
64位数字重复这个过程即可,回头看golang的代码应该就可以看懂了,这里就不再详细解释了。
另外这个算法过程还可以进一步优化,详细可以参考下:计算汉明权重的SWAR(SIMD within a Register)算法 感兴趣的可以研究一下,这里就不赘述了。
4. POPCNT指令
一些较新的CPU上支持POPCNT
指令,可以通过硬件直接进行计算,Golang代码示例如下:
main.go文件
package main
import (
"fmt"
"math/bits"
"math/rand"
"time"
)
func main() {
rand.Seed(time.Now().Unix())
for i := 0; i < 100; i++ {
var num = rand.Uint64()
if popcnt(num) != bits.OnesCount64(num) {
panic(fmt.Sprintf("i: %d, popcnt(%b) = %d, bits.OnesCount64(%b) = %d", i, num, popcnt(num), num, bits.OnesCount64(num)))
}
}
fmt.Println("ok")
}
func popcnt(x uint64) int
amd64.s 文件
#include "textflag.h"
TEXT main·popcnt(SB), NOSPLIT, $0-8
MOVQ x+0(FP), AX // 将参数x移到AX寄存器
BYTE $0xf3; BYTE $0x48; BYTE $0x0f; BYTE $0xb8; BYTE $0xc0 // 计算二进制X中1的个数,golang编译器不支持POPCNT指令,这行对应于POPCNT AX, AX
MOVQ AX, ret+8(FP) // 将结果存入ret
RET