go - 有 big.BitCount 吗？

Question

是否已经为 big.Int 编写了 BitCount 方法？ math/big好像没有。

显然，如果没有，我会自己写一个 - 有人已经写过吗？

我想要数字中设置的位数。喜欢Java BigInteger.bitCount() .

Answer 1

如前所述，为了快速有效地原始访问 big.Int 的底层位你想用 big.Bits .此外，比 8 位查找表或简单循环更快的是使用众所周知的 64 位计数方法之一(又名 Hamming weight )。更快，您可以使用 popcount 的汇编实现使用 native CPU instruction ¹.

不使用汇编，或迎合已知设置的位很少的特殊情况，这可能是更快/最快的 Go 实现之一(通过使用 uint32 并调整popcount 相应的功能):

func BitCount(n *big.Int) int {
    count := 0
    for _, v := range n.Bits() {
        count += popcount(uint64(v))
    }
    return count
}

// Straight and simple C to Go translation from https://en.wikipedia.org/wiki/Hamming_weight
func popcount(x uint64) int {
    const (
        m1  = 0x5555555555555555 //binary: 0101...
        m2  = 0x3333333333333333 //binary: 00110011..
        m4  = 0x0f0f0f0f0f0f0f0f //binary:  4 zeros,  4 ones ...
        h01 = 0x0101010101010101 //the sum of 256 to the power of 0,1,2,3...
    )
    x -= (x >> 1) & m1             //put count of each 2 bits into those 2 bits
    x = (x & m2) + ((x >> 2) & m2) //put count of each 4 bits into those 4 bits
    x = (x + (x >> 4)) & m4        //put count of each 8 bits into those 8 bits
    return int((x * h01) >> 56)    //returns left 8 bits of x + (x<<8) + (x<<16) + (x<<24) + ...
}

这里介绍的这个和其他实现的基准和比较可以在 GitHub gist 上完整获得。 .

¹ 例如 one added in Go1.9 ;更新后的要点显示它比我之前最好的快了约 3 倍。