1

BitCountbig.Int是否有已经编写好的方法？数学/大似乎没有一个。

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

我想要数字中设置的位数。就像Java BigInteger.bitCount()一样。

4

4 回答 4

6

如前所述，为了快速有效地原始访问big.Int您要使用的 a 的底层位big.Bits。此外，比 8 位查找表或简单循环更快的是使用众所周知的 64 位计数方法之一（又名汉明权重）。popcount甚至更快，您可以使用使用本机CPU 指令¹的汇编实现。

不使用汇编，或迎合已知设置很少位的特殊情况，这可能是更快/最快的 Go 实现之一（通过使用uint32和相应地调整popcount函数，它可以在 32 位机器上变得更快）：

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上完整获取。

¹ 如Go1.9 中添加的那个；更新后的要点显示它比我之前最好的速度快了约 3 倍。

于 2015-09-21T18:38:04.567 回答
3

I put one together myself - note that this does not take into account the sign of the number. This returns the bit count of the the raw bytes behind the big.Int.

// How many bits?
func BitCount(n big.Int) int {
    var count int = 0
    for _, b := range n.Bytes() {
        count += int(bitCounts[b])
    }
    return count
}

// The bit counts for each byte value (0 - 255).
var bitCounts = []int8{
    // Generated by Java BitCount of all values from 0 to 255
    0, 1, 1, 2, 1, 2, 2, 3, 
    1, 2, 2, 3, 2, 3, 3, 4, 
    1, 2, 2, 3, 2, 3, 3, 4, 
    2, 3, 3, 4, 3, 4, 4, 5, 
    1, 2, 2, 3, 2, 3, 3, 4, 
    2, 3, 3, 4, 3, 4, 4, 5,  
    2, 3, 3, 4, 3, 4, 4, 5, 
    3, 4, 4, 5, 4, 5, 5, 6, 
    1, 2, 2, 3, 2, 3, 3, 4, 
    2, 3, 3, 4, 3, 4, 4, 5, 
    2, 3, 3, 4, 3, 4, 4, 5, 
    3, 4, 4, 5, 4, 5, 5, 6, 
    2, 3, 3, 4, 3, 4, 4, 5, 
    3, 4, 4, 5, 4, 5, 5, 6, 
    3, 4, 4, 5, 4, 5, 5, 6, 
    4, 5, 5, 6, 5, 6, 6, 7, 
    1, 2, 2, 3, 2, 3, 3, 4, 
    2, 3, 3, 4, 3, 4, 4, 5, 
    2, 3, 3, 4, 3, 4, 4, 5, 
    3, 4, 4, 5, 4, 5, 5, 6, 
    2, 3, 3, 4, 3, 4, 4, 5, 
    3, 4, 4, 5, 4, 5, 5, 6, 
    3, 4, 4, 5, 4, 5, 5, 6, 
    4, 5, 5, 6, 5, 6, 6, 7, 
    2, 3, 3, 4, 3, 4, 4, 5, 
    3, 4, 4, 5, 4, 5, 5, 6, 
    3, 4, 4, 5, 4, 5, 5, 6, 
    4, 5, 5, 6, 5, 6, 6, 7, 
    3, 4, 4, 5, 4, 5, 5, 6, 
    4, 5, 5, 6, 5, 6, 6, 7, 
    4, 5, 5, 6, 5, 6, 6, 7, 
    5, 6, 6, 7, 6, 7, 7, 8,
}
于 2013-10-01T21:21:52.370 回答
3

您现在可以使用（从 Go 1.9 开始）math/bits实现一些处理位相关计算的有用函数的库。具体来说，您可以遍历big.Int.Bits并调用bits.OnesCount函数的结果。

这是一个例子：

package main

import (
    "fmt"
    "math/big"
    "math/bits"
)

func BitCount(z *big.Int) int {
    var count int
    for _, x := range z.Bits() {
        count += bits.OnesCount(uint(x))
    }
    return count
}

func PrintBinary(z *big.Int) {
    for _, x := range z.Bits() {
        fmt.Printf("%064b\n", x)
    }
}

func main() {
    a := big.NewInt(1 << 60 - 1)
    b := big.NewInt(1 << 61 - 1)
    c := big.NewInt(0)
    c = c.Mul(a, b)

    fmt.Println("Value in binary format:")
    PrintBinary(c)
    fmt.Println("BitCount:", BitCount(c))
}
于 2018-02-13T16:00:43.757 回答
2

仅供参考，以下解决方案比此处提供的原始解决方案更简单、更快：

func BitCountFast(z *big.Int) int {
    var count int
    for _, x := range z.Bits() {
            for x != 0 {
                    x &= x-1
                    count++
            }
    }
    return count
}

在我的机器上，它的性能比原来的解决方案高 5 倍：

BenchmarkBitCountFast-4 100000000           19.5 ns/op         0 B/op          0 allocs/op
BenchmarkBitCountOrig-4 20000000            96.1 ns/op        16 B/op          1 allocs/op
于 2015-09-21T12:52:55.617 回答