统计一个数字二进制位1的个数

Tag Go
Posted on
View

最近一个需求需要使用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
}

计算过程如图: image.png

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
}

计算过程如下: image.png

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

来都来了说句话再走呗