# Efficient Bit Manipulation in Go 1.9

Go 1.9, released in August 2017, introduced the `maths/bits` package. This package provides optimized functions for bit counting and manipulation of unsigned integers. These are useful in low-level environments where the individual bits stored in an integer are of importance. Let’s take a look at some of the functions.

First up, `Len` returns the minimum number of bits required to represent a value `x`.

``````package main

import (
"fmt"
"math/bits"
)

func main() {
var a uint = 31
fmt.Printf("bits.Len(%d) = %d\n", a, bits.Len(a))

a++
fmt.Printf("bits.Len(%d) = %d\n", a, bits.Len(a))
}
``````

Which outputs:

``````bits.Len(31) = 5
bits.Len(32) = 6
``````

Playground link

This is because 31 is `11111` in binary, and 32 is `100000`. The first significant bit is in each case is in position 5 and 6, respectively, when counting positions from the right.

This also allows us to easily illustrate the `OnesCount` function, which returns the number of bits set to 1 in a given number:

``````package main

import (
"fmt"
"math/bits"
)

func main() {
var a uint = 31
fmt.Printf("bits.OnesCount(%d) = %d\n", a, bits.OnesCount(a))

a++
fmt.Printf("bits.OnesCount(%d) = %d\n", a, bits.OnesCount(a))
}
``````

which outputs:

``````bits.OnesCount(31) = 5
bits.OnesCount(32) = 1
``````

Playground link

We also have `LeadingZeros`, `TrailingZeros`, `Reverse` and `ReverseBytes`. Let’s use all of these in a single program to demonstrate how they work. In the next example, we use the `uint16` version of these functions to keep the output short and readable. We could just as easily use the 32-bit, 64-bit or unspecified versions.

``````package main

import (
"fmt"
"math/bits"
"os"
"text/tabwriter"
)

func main() {
// read an unsigned integer from stdin
var i uint16
_, err := fmt.Scanf("%d", &i)
if err != nil {
i = 100
fmt.Println("Defaulting to 100")
}

// create a tabwriter for formatting the output
w := new(tabwriter.Writer)

// Format in tab-separated columns with a tab stop of 8.
w.Init(os.Stdout, 0, 8, 0, '\t', 0)

fmt.Fprintf(w, "Binary:\t%0.16bb\n", i)
fmt.Fprintf(w, "Len:\t%16d\n", bits.Len16(i))
fmt.Fprintf(w, "Ones count:\t%16d\n", bits.OnesCount16(i))
fmt.Fprintf(w, "Leading zeros:\t%16d\n", bits.LeadingZeros16(i))
fmt.Fprintf(w, "Trailing zeros:\t%16d\n", bits.TrailingZeros16(i))
fmt.Fprintf(w, "Reversed:\t%0.16bb\n", bits.Reverse16(i))
fmt.Fprintf(w, "Reversed Bytes:\t%0.16bb\n", bits.ReverseBytes16(i))

w.Flush()
}
``````

An example run with 123 as the input gives us the following:

``````\$ go run bits.go
123
Binary:         0000000001111011b
Len:                           7
Ones count:                    6
Leading zeros:                 9
Trailing zeros:                0
Reversed:       1101111000000000b
Reversed Bytes: 0111101100000000b
``````

Playground Link

It’s not difficult to see what these functions do: `LeadingZeros` returns the number of zeros to the left of the most significant set bit. `TrailingZeros` returns the number of zeros to the right of the least significant set bit. `Reverse` returns the number with all bits in reverse order, and `ReverseBytes` reverses the number byte-by-byte, that is, in 8-bit blocks.

## How does it perform? #

This is all good and well, and it can be useful at times. But some of these functions are relatively simple to implement manually. How much more efficient are the library implementations, really?

Let’s compare the performance of `OnesCount64` with that of a naive algorithm for counting the number of set bits. Below is a simple benchmark that compares a naive implementation of `OnesCount64`, which uses bit shifting to count the number of set bits, to the built-in `bits.OnesCount64`:

``````package main

import (
"math/bits"
"testing"
)

func NaiveOnesCount64(x uint64) int {
var c, i uint64
for i = 0; i < 64; i++ {
c += (x >> i) & 1
}
return int(c)
}

var numbers = []uint64{
0, 1, 2, 3, 4, 5, 6, 7, 8, 9,
100, 200, 300, 400, 500, 600, 700, 800, 900,
11111, 22222, 33333, 44444, 55555, 66666, 77777, 88888, 99999,
190239012390, 123901312, 6549654, 45904059,
}

// Output is a global sync variable so that test outputs
// do not get elided by the compiler.
var Output int

func TestNaiveOnesCount64(t *testing.T) {
m := len(numbers)
for n := 0; n < m; n++ {
x := numbers[n%m]
got := NaiveOnesCount64(x)
want := bits.OnesCount64(x)
if got != want {
t.Errorf("NaiveOnesCount64(%d) = %d, want %d", x, got, want)
}
}
}

func BenchmarkNaiveOnesCount64(b *testing.B) {
// run NaiveOnesCount b.N times
var s int
for n := 0; n < b.N; n++ {
// use &31 to avoid modulo operation
s += NaiveOnesCount64(numbers[n&31])
}
Output = s
}

func BenchmarkBitsOnesCount64(b *testing.B) {
// run NaiveOnesCount b.N times
var s int
for n := 0; n < b.N; n++ {
// use &31 to avoid modulo operation
s += bits.OnesCount64(numbers[n&31])
}
Output = s
}
``````

Running the comparison on a 64-bit Linux machine, we get:

``````\$ go test -bench=Count
goos: linux
goarch: amd64
BenchmarkNaiveOnesCount64-4     20000000            71.6 ns/op
BenchmarkBitsOnesCount64-4      2000000000           1.15 ns/op
PASS
ok      _/home/code/bits    3.946s
``````

The built-in `OnesCount` is orders of magnitude faster! This is because the built-in function uses an algorithm called Parallel summing of adjacent bits. A full description of this is given in Chapter 5 of Hacker’s Delight, Counting Bits. (Correction: on x86-64 systems, it actually uses POPCNT instructions, see note at bottom of this post).

Below is another benchmark comparison, this time for `TrailingZeros64`:

``````package main

import (
"math/bits"
"testing"
)

// NaiveTrailingZeros64 returns the number of trailing zero bits in x;
// the result is 64 for x == 0.
func NaiveTrailingZeros64(x uint64) int {
var c, i uint64
for i = 0; i < 64; i++ {
if (x>>i)&1 == 1 {
break
}
c++
}
return int(c)
}

var nums = []uint64{
0, 1, 2, 3, 4, 5, 6, 7, 8, 9,
100, 200, 300, 400, 500, 600, 700, 800, 900,
11111, 22222, 33333, 44444, 55555, 66666, 77777, 88888, 99999,
190239012390, 123901312, 6549654, 45904059,
}

// Output is a global sync variable so that test outputs
// do not get elided by the compiler.
var Output int

func TestNaiveTrailingZeros64(t *testing.T) {
m := len(nums)
for n := 0; n < m; n++ {
x := nums[n%m]
got := NaiveTrailingZeros64(x)
want := bits.TrailingZeros64(x)
if got != want {
t.Errorf("NaiveTrailingZeros64(%d) = %d, want %d", x, got, want)
}
}
}

func BenchmarkNaiveTrailingZeros64(b *testing.B) {
// run NaiveOnesCount b.N times
s := 0
for n := 0; n < b.N; n++ {
s += NaiveTrailingZeros64(nums[n&31])
}
Output = s
}

func BenchmarkBitsTrailingZeros64(b *testing.B) {
// run NaiveOnesCount b.N times
s := 0
for n := 0; n < b.N; n++ {
s += bits.TrailingZeros64(nums[n&31])
}
Output = s
}

``````

Running this we get:

``````\$ go test -bench=Trailing
goos: linux
goarch: amd64
BenchmarkNaiveTrailingZeros64-4     300000000            5.86 ns/op
BenchmarkBitsTrailingZeros64-4      2000000000           1.00 ns/op
PASS
ok      _/home/code/bits    4.460s
``````

Again, we see that `TrailingZeros64` is significantly more efficient than the naive solution, though not by as much in this case. This time the reason is that it implements an algorithm first described by Charles E. Leiserson, Harald Prokop and Keith H. Randallin in 1998, using what is called De Bruijn numbers. It’s a neat trick, and I recommend reading the original paper. (Correction: Again, it was pointed out that this is not true on most 64-bit systems, see note at the bottom of post)

## Example Use Case #

Now that we have seen that the built-in functions are much faster, you may still be asking “why should I care?” Bit manipulation isn’t all that common of a thing to need, and we still have to shift left and right with the `<<` and `>>` operators when we do need it, so this is a fair question.

One example where this has already made an impact is in Will Fitzgerald’s bitset package. A blog post by Daniel Lemire shows how changing to use the new bits package made the `Count` function run twice as fast, and the previous implementation relied on hand-tuned assembly code!

``````\$ go test -run=XXX -bench Count >old.txt
\$ git checkout go19
\$ go get golang.org/x/tools/cmd/benchcmp
\$ go test -run=XXX -bench Count >new.txt
\$ benchcmp old.txt new.txt
benchmark                  old ns/op     new ns/op     delta
BenchmarkCount-4           2676          1352          -49.48%
BenchmarkLemireCount-4     2569228       1401137       -45.46%
``````

Bitsets are commonly used in all sorts of applications that are memory or space-aware, from databases (e.g. bloom filters) to priority queues and examining stream data. The use of the new `bits` package in bitsets provides an example of the positive impact this will have on the performance of many Go applications.

## Conclusion #

The new bit manipulation package in Go 1.9 wasn’t celebrated all that much, but it is pretty exciting if you do low-level programming in Go. It can provide quick efficiency gains if you are already using some of these common functions in a hot path in your code. Kudos to Robert Griesemer, Roman Budnikov and Lynn Boger, who worked on getting this into the standard library.

Update: some great feedback from giovannibajo and klauspost on r/golang - apparently a lot of the efficiency of the OnesCount and TrailingZeros on 64-bit systems comes from calling POPCNT and BSF instructions when the CPU supports it. The algorithms mentioned in the article are a fallback if the system does not support these methods.

I’m a London-based software engineer who likes writing (about) Go. If you like this article, feel free to reach out on Twitter; over there I’m known as @ironzeb. I’m currently writing Production Go, a book that walks through building a modern production-ready application Go.

### The Popularity of Go

When you look at the Google Trends graph above, it would seem like the Go programming language, also known as Golang, is on its way to big things. But let’s not get ahead of ourselves, Go fans. Let’s first have a cup of java to put... Continue →