1

BitCountbig.Int 用に既に作成されたメソッドはありますか? math/big にはないようです。

明らかに、そうでない場合は自分で書きます-誰かがすでに書いていますか？

数値に設定されたビット数が必要です。Java BigInteger.bitCount()と同様です。

4

4 に答える 4

6

big.Int既に述べたように、使用したいa の基礎となるビットへの素早い効率的な raw アクセスのためにbig.Bits. また、8 ビットのルックアップ テーブルや単純なループよりも高速なのは、ビットをカウントするよく知られた 64 ビットの方法 (別名ハミング重み) の 1 つを使用することです。popcountさらに高速に、ネイティブCPU 命令を使用する のアセンブリ実装を使用できます¹。

uint32アセンブリを使用せずに、または少数のビットが設定されていることが知られている特別なケースにケータリングしない場合、これはおそらく最も高速/最速の Go 実装の 1 つです (32 ビット マシンでは、関数を使用して適宜調整することで高速化できます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で完全に入手できます。

¹ Go1.9 で追加されたものなど。更新された要点は、以前の最高の速度よりも ~3 倍高速であることを示しています。

于 2015-09-21T18:38:04.567 に答える
3

私は自分で1つをまとめました-これは数の符号を考慮していないことに注意してください. これは、 の後ろの raw バイトのビット カウントを返します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 に答える
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 に答える