有没有一个已经写好的大BitCount方法。国际？数学/大似乎没有。
显然，如果没有，我会自己写一个 - 有人已经写过了吗？
我想要数字中的设置位数。像Java BigInteger.bitCount（）。
如前所述，为了快速有效地原始访问big.Int的基础位，您需要使用big.Bits .此外，比 8 位查找表或简单循环更快的是使用众所周知的 64 位方法来计算位（又名汉明权重）。更快，您可以使用使用本机 CPU 指令¹的 popcount 程序集实现。
不使用汇编，或者迎合已知设置很少位的特殊情况，这可能是更快/最快的 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×。
你现在可以使用（从 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("%064bn", 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))
}
我自己把一个放在一起 - 请注意，这没有考虑数字的符号。这将返回 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,
}
仅
供参考，以下解决方案比此处提供的原始解决方案更简单、更快捷：
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