有big.BitCount吗？

Question

有一个已经写好的BitCount方法用于big.Int吗？在数学/大部头上似乎没有一个。

显然，如果没有，我会亲自写一个--有人已经写好了吗？

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

Answer 1

我自己整理了一个--注意，这确实是，而不是，考虑到了数字的符号。这将返回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,
}

Answer 2

如前所述，为了快速、有效地原始访问big.Int的底层位，您需要使用big.Bits。另外，与8位查找表或简单循环相比，更快的是使用熟悉的64位方法中的一种来计数比特(又名Hamming重量)。更快的是，您可以使用使用本机popcount 1的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要点上完整地获得。

例如一项加在Go1.9中；更新的要点显示它比以前最好的要快3×10。

Answer 3

您现在可以使用math/bits库(从Go 1.9开始)，它实现了一些处理与位相关的计算的有用函数。具体来说，您可以迭代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))
}