Есть ли Big.BitCount?

Есть ли уже написано BitCount метод для биг. Там, кажется, не один в математике / большой.

Очевидно, я сам напишу, если нет - кто-нибудь уже написал?

Я хочу количество установленных бит в числе. Как и Java BigInteger.bitCount ().

Источник

4 ответа

Решение

Я сам собрал один - обратите внимание, что это не учитывает знак числа. Это возвращает количество бит необработанных байтов за 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,
}
Источник

Как уже упоминалось, для быстрого эффективного необработанного доступа к основным битам big.Int ты хочешь использовать big.Bits, Кроме того, быстрее, чем 8-битная таблица поиска или простой цикл, нужно использовать один из хорошо известных 64-битных методов подсчета битов (он же вес Хэмминга). Еще быстрее, вы можете использовать сборочную реализацию popcount который использует встроенную инструкцию процессора ¹.

Без использования сборки или удовлетворения особых случаев, когда известно, что установлено несколько битов, это, вероятно, одна из самых быстрых / быстрых реализаций Go (это можно сделать быстрее на 32-битных машинах с помощью 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.

¹ Например, добавленный в 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("%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))
}
Источник

К вашему сведению, следующее решение проще и быстрее, чем оригинальное решение, представленное здесь:

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
Источник
Другие вопросы по тегам