Exploring implementations of `func BitCount(*big.Int) int` in Go

bench.out

goos: freebsd
goarch: amd64
pkg: dave-test/_test/big_bitcount
BenchmarkBitCountGo19 	20000000	       364 ns/op	       0 B/op	       0 allocs/op
BenchmarkBitCount     	 1000000	      7024 ns/op	    4096 B/op	       1 allocs/op
BenchmarkBitCountW    	 3000000	      2276 ns/op	       0 B/op	       0 allocs/op
BenchmarkBitCountF    	  500000	     13384 ns/op	       0 B/op	       0 allocs/op
BenchmarkBitCount1    	 5000000	      1562 ns/op	       0 B/op	       0 allocs/op
BenchmarkBitCount2    	 5000000	      1245 ns/op	       0 B/op	       0 allocs/op
BenchmarkBitCount3    	10000000	       947 ns/op	       0 B/op	       0 allocs/op
PASS
ok  	dave-test/_test/big_bitcount	58.038s

bitcount.go

package bitcount

import "math/big"

// This is basicly the implementation shown at http://stackoverflow.com/a/19126170/55504

// BitCount returns the number of 'one' bits in n.
// It does not account for the sign of the n.
func BitCount(n *big.Int) int {
	count := 0
	for _, b := range n.Bytes() {
		count += int(bitCounts[b])
	}
	return count
}

// This variation shows the difference between the Bytes and Bits methods.

func BitCountW(n *big.Int) int {
	count := 0
	for _, v := range n.Bits() {
		v := uint64(v)
		count += int(bitCounts[(v>>0)&0xff])
		count += int(bitCounts[(v>>8)&0xff])
		count += int(bitCounts[(v>>16)&0xff])
		count += int(bitCounts[(v>>24)&0xff])
		count += int(bitCounts[(v>>32)&0xff])
		count += int(bitCounts[(v>>40)&0xff])
		count += int(bitCounts[(v>>48)&0xff])
		count += int(bitCounts[(v>>56)&0xff])
	}
	return count
}

// The bit counts for each byte value (0 - 255).
var bitCounts = []int8{
	// Pre-generated values
	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,
}

bitcount2.go

package bitcount

import "math/big"

// The implementation from http://stackoverflow.com/a/32695740/55504

func BitCountFast(z *big.Int) int {
	var count int
	for _, x := range z.Bits() {
		for x != 0 {
			x &= x - 1
			count++
		}
	}
	return count
}

// These are trivial wrappers to popcountN…

func BitCount1(n *big.Int) int {
	count := 0
	for _, v := range n.Bits() {
		count += popcount1(uint64(v))
	}
	return count
}

func BitCount2(n *big.Int) int {
	count := 0
	for _, v := range n.Bits() {
		count += popcount2(uint64(v))
	}
	return count
}

func BitCount3(n *big.Int) int {
	count := 0
	for _, v := range n.Bits() {
		count += popcount3(uint64(v))
	}
	return count
}

// Straight and simple C to Go translation from https://en.wikipedia.org/wiki/Hamming_weight

// constants used in the functions below
const (
	m1  = 0x5555555555555555 //binary: 0101...
	m2  = 0x3333333333333333 //binary: 00110011..
	m4  = 0x0f0f0f0f0f0f0f0f //binary:  4 zeros,  4 ones ...
	m8  = 0x00ff00ff00ff00ff //binary:  8 zeros,  8 ones ...
	m16 = 0x0000ffff0000ffff //binary: 16 zeros, 16 ones ...
	m32 = 0x00000000ffffffff //binary: 32 zeros, 32 ones
	hff = 0xffffffffffffffff //binary: all ones
	h01 = 0x0101010101010101 //the sum of 256 to the power of 0,1,2,3...
)

// This is a naive implementation, shown for comparison,
// and to help in understanding the better functions.
// It uses 24 arithmetic operations (shift, add, and).
func popcount1(x uint64) int {
	x = (x & m1) + ((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 & m4) + ((x >> 4) & m4)    //put count of each  8 bits into those  8 bits
	x = (x & m8) + ((x >> 8) & m8)    //put count of each 16 bits into those 16 bits
	x = (x & m16) + ((x >> 16) & m16) //put count of each 32 bits into those 32 bits
	x = (x & m32) + ((x >> 32) & m32) //put count of each 64 bits into those 64 bits
	return int(x)
}

// This uses fewer arithmetic operations than any other known
// implementation on machines with slow multiplication.
// It uses 17 arithmetic operations.
func popcount2(x uint64) int {
	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
	x += x >> 8                    //put count of each 16 bits into their lowest 8 bits
	x += x >> 16                   //put count of each 32 bits into their lowest 8 bits
	x += x >> 32                   //put count of each 64 bits into their lowest 8 bits
	return int(x & 0x7f)
}

// This uses fewer arithmetic operations than any other known
// implementation on machines with fast multiplication.
// It uses 12 arithmetic operations, one of which is a multiply.
func popcount3(x uint64) int {
	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) + ...
}

bitcount_go19_test.go

// +build go1.9

package bitcount

import (
	"math/big"
	"math/bits"
	"testing"
)

func BitCountBitsOnesCount64(n *big.Int) int {
	count := 0
	for _, v := range n.Bits() {
		count += bits.OnesCount64(uint64(v))
	}
	return count
}

func TestBitCountGo19(t *testing.T)      { testBitCounter(t, BitCountBitsOnesCount64) }
func BenchmarkBitCountGo19(b *testing.B) { benchBitCounter(b, BitCountBitsOnesCount64) }

bitcount_test.go

package bitcount

import (
	"math/big"
	"math/rand"
	"testing"
)

var testInt = genBigInt(0, 8<<10)

// genBigInt generates a repeatable pseudo-random big.Int
func genBigInt(seed int64, maxlen int) *big.Int {
	src := rand.NewSource(seed)
	rng := rand.New(src)
	l := rng.Intn(maxlen)
	b := make([]byte, l+3)
	for i := 0; i < l; i += 4 {
		x := rng.Int63()
		b[i+0] = byte((x >> 0) & 0xff)
		b[i+1] = byte((x >> 8) & 0xff)
		b[i+2] = byte((x >> 16) & 0xff)
		b[i+3] = byte((x >> 24) & 0xff)
	}
	return big.NewInt(0).SetBytes(b[:l])
}

func testBitCounter(t *testing.T, fn func(*big.Int) int) {
	tests := []struct {
		in  *big.Int
		out int
	}{
		{big.NewInt(0), 0},
		{big.NewInt(1), 1},
		{big.NewInt(2), 1},
		{big.NewInt(3), 2},
		{big.NewInt(123456789), 16},
		{testInt, 16437},
	}
	for i, d := range tests {
		if e, g := d.out, fn(d.in); e != g {
			t.Errorf("%2d: BitCount(%v) gave %v, want %v\n", i, d.in, g, e)
		}
	}
}

func benchBitCounter(b *testing.B, fn func(*big.Int) int) {
	b.ReportAllocs()
	for i := 0; i < b.N; i++ {
		_ = fn(testInt)
	}
}

func TestBitCount(t *testing.T)  { testBitCounter(t, BitCount) }
func TestBitCountW(t *testing.T) { testBitCounter(t, BitCountW) }
func TestBitCountF(t *testing.T) { testBitCounter(t, BitCountFast) }
func TestBitCount1(t *testing.T) { testBitCounter(t, BitCount1) }
func TestBitCount2(t *testing.T) { testBitCounter(t, BitCount2) }
func TestBitCount3(t *testing.T) { testBitCounter(t, BitCount3) }

func BenchmarkBitCount(b *testing.B)  { benchBitCounter(b, BitCount) }
func BenchmarkBitCountW(b *testing.B) { benchBitCounter(b, BitCountW) }
func BenchmarkBitCountF(b *testing.B) { benchBitCounter(b, BitCountFast) }
func BenchmarkBitCount1(b *testing.B) { benchBitCounter(b, BitCount1) }
func BenchmarkBitCount2(b *testing.B) { benchBitCounter(b, BitCount2) }
func BenchmarkBitCount3(b *testing.B) { benchBitCounter(b, BitCount3) }