gobitcount

Is there a big.BitCount?


Is there an already-written BitCount method for big.Int? There doesn't seem to be one in math/big.

Obviously I will write one myself if not - does anyone have one already written?

I want the number of set bits in the number. Like Java BigInteger.bitCount().


Solution

  • 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,
    }