Bit Manipulation in Go With Real and Practical Examples

Bit manipulation shows up in Go less than in C, and it shows up in exactly the places where nothing else works: flags packed into a byte, protocol headers, compact sets of small integers, hash functions, permissions. The operators are few and the idioms around them are older than the language. This guide covers the operators with their output, the four operations you do on a single bit, the helpers in math/bits, three worked examples, a flag set, a packed color and a bitset, and the shifts that go wrong. It builds on integer types and overflow and iota flags, and it belongs to the Go basics path. For quick checks, the bitwise calculator and the number base converter show the bits of a value.

The operators

Go's bitwise operators work on integer types, bit by bit. This program applies each to two small values and prints them in binary, so you can read the result against the operands:

package main

import "fmt"

func main() {
	a, b := uint8(0b1100_1010), uint8(0b1010_0110)

	fmt.Printf("a      = %08b\n", a)
	fmt.Printf("b      = %08b\n", b)
	fmt.Printf("a & b  = %08b\n", a&b)
	fmt.Printf("a | b  = %08b\n", a|b)
	fmt.Printf("a ^ b  = %08b\n", a^b)
	fmt.Printf("a &^ b = %08b\n", a&^b)
	fmt.Printf("^a     = %08b\n", ^a)
	fmt.Printf("a << 2 = %08b\n", a<<2)
	fmt.Printf("a >> 3 = %08b\n", a>>3)

	var s int8 = -8
	fmt.Println(s>>1, s>>10, uint8(s)>>1)
}

a      = 11001010
b      = 10100110
a & b  = 10000010
a | b  = 11101110
a ^ b  = 01101100
a &^ b = 01001000
^a     = 00110101
a << 2 = 00101000
a >> 3 = 00011001
-4 -1 124

& keeps bits set in both, | keeps bits set in either, and ^ between two operands keeps bits that differ. Used on its own, ^a is bitwise NOT, flipping every bit, which for an unsigned type gives the complement. &^ is the operator Go adds that C does not have: it clears from the left operand every bit that is set in the right one, so a &^ b is the same as a & ^b and reads as "a, without b". The shifts move bits and fill with zeros, and bits shifted past the width are lost, so a << 2 printed 00101000, with the top two bits gone.

The last line shows the difference between shifting signed and unsigned values. A signed right shift is arithmetic: it copies the sign bit, so -8 >> 1 is -4, and shifting by more than the width gives -1. The unsigned shift fills with zeros. Cast to uint8 first if you want the bit pattern shifted logically. The literal 0b1100_1010 uses the binary prefix and digit separators, both Go 1.13 features that make bit patterns readable.

The four single-bit operations

Everything you do to one bit is a mask and one of three operators. The mask for bit n is 1 << n:

• Set bit n: x | (1 << n) forces it to one.
• Clear bit n: x &^ (1 << n) forces it to zero.
• Toggle bit n: x ^ (1 << n) flips it.
• Test bit n: x & (1 << n) != 0 is true when it is set.

That is the entire idiom. As functions on a flag byte, with named bit positions:

package main

import "fmt"

type Flags uint8

const (
	Read Flags = 1 << iota
	Write
	Exec
	Hidden
)

func (f Flags) Has(m Flags) bool     { return f&m != 0 }
func (f Flags) Set(m Flags) Flags    { return f | m }
func (f Flags) Clear(m Flags) Flags  { return f &^ m }
func (f Flags) Toggle(m Flags) Flags { return f ^ m }

func main() {
	var f Flags
	f = f.Set(Read | Write)
	fmt.Printf("%04b has write: %t, has exec: %t\n", f, f.Has(Write), f.Has(Exec))

	f = f.Toggle(Exec).Clear(Write)
	fmt.Printf("%04b\n", f)

	fmt.Println(f.Has(Read|Exec), f.Has(Read|Write))
}

0011 has write: true, has exec: false
0101
true true

The methods take a mask that may hold several bits. Has(Read|Exec) is true only if the single & with the combined mask is non-zero, which tests whether any of them is set, and that is a subtle point: if you mean "all of these are set", write f&m == m. The example's last line shows the "any" meaning, so Has(Read|Write) is true even though Write was cleared. Bit flags built this way are the same as the flag sets in the standard library, such as os.FileMode and the flags to os.OpenFile you met in reading and writing files.

Useful tricks

A few identities come up often enough to memorize. n & (n-1) clears the lowest set bit of n, so repeating it until the value is zero counts the bits. It follows that n&(n-1) == 0 is true when n is zero or a power of two, which is the standard power-of-two test. n & -n isolates the lowest set bit, because the two's complement negative flips every bit above it. x ^ x is zero, and three xors swap two values without a temporary, though a, b = b, a is clearer and the compiler does better with it.

The math/bits package

The math/bits package wraps operations that CPUs implement as single instructions, and it is the right tool whenever you would otherwise write a loop:

package main

import (
	"fmt"
	"math/bits"
)

func main() {
	x := uint32(0b0001_0110_0000)

	fmt.Println(bits.OnesCount32(x), bits.Len32(x), bits.LeadingZeros32(x), bits.TrailingZeros32(x))
	fmt.Printf("%032b\n", bits.RotateLeft32(x, 4))
	fmt.Printf("%032b\n", bits.Reverse32(x))
	fmt.Println(bits.UintSize, bits.OnesCount8(0xFF), bits.Len(0))

	hi, lo := bits.Mul64(1<<63, 4)
	fmt.Println(hi, lo)
}

3 9 23 5
00000000000000000001011000000000
00000110100000000000000000000000
64 8 0
2 0

OnesCount is the population count, and Len is the number of bits needed to represent the value, which equals the position of the highest set bit plus one. LeadingZeros and TrailingZeros count from each end. RotateLeft moves bits around the word instead of dropping them, and a negative count rotates right. Reverse mirrors the bit order. The Mul64 line shows the carry-aware arithmetic from integer overflow: 1<<63 * 4 overflows 64 bits, and the function returns the high and low words, 2 and 0. Use these instead of hand-written loops. They are shorter, they are tested, and on x86 and ARM they turn into one instruction.

Packing values into an integer

Packing small fields into one word is the oldest use of bit operations and it is still how colors, IP addresses and network headers are handled. Here is a color, with each channel in one byte, packed into a uint32:

package main

import "fmt"

type RGBA uint32

func pack(r, g, b, a uint8) RGBA {
	return RGBA(r)<<24 | RGBA(g)<<16 | RGBA(b)<<8 | RGBA(a)
}

func (c RGBA) Channels() (r, g, b, a uint8) {
	return uint8(c >> 24), uint8(c >> 16), uint8(c >> 8), uint8(c)
}

func (c RGBA) WithAlpha(a uint8) RGBA { return c&^0xFF | RGBA(a) }

func main() {
	c := pack(255, 128, 0, 255)
	fmt.Printf("%#08x\n", uint32(c))
	fmt.Println(c.Channels())

	half := c.WithAlpha(127)
	fmt.Printf("%#08x\n", uint32(half))
}

0xff8000ff
255 128 0 255
0xff80007f

Packing shifts each channel to its position and ORs them together. Unpacking shifts right and converts to uint8, which truncates to the low eight bits, so no mask is needed, a property of integer conversions from type conversion. WithAlpha clears the low byte with &^ 0xFF and ORs in the new value. Widening each uint8 to the RGBA type before shifting is essential: uint8(r) << 24 would shift the value out of its own eight bits and produce zero. This is the single most common bug in hand-rolled packing code.

A bitset type

A set of small non-negative integers fits in a slice of uint64 words, one bit per member. It uses 64 times less memory than a map[int]bool for dense sets and is faster for union and intersection:

package bitset

import "math/bits"

type Set struct {
	words []uint64
}

func (s *Set) Add(i int) {
	w := i / 64
	for len(s.words) <= w {
		s.words = append(s.words, 0)
	}
	s.words[w] |= 1 << (i % 64)
}

func (s *Set) Has(i int) bool {
	w := i / 64
	return w < len(s.words) && s.words[w]&(1<<(i%64)) != 0
}

func (s *Set) Remove(i int) {
	if w := i / 64; w < len(s.words) {
		s.words[w] &^= 1 << (i % 64)
	}
}

func (s *Set) Len() int {
	n := 0
	for _, w := range s.words {
		n += bits.OnesCount64(w)
	}
	return n
}

func (s *Set) Union(o *Set) {
	for len(s.words) < len(o.words) {
		s.words = append(s.words, 0)
	}
	for i, w := range o.words {
		s.words[i] |= w
	}
}

package bitset

import "testing"

func TestSet(t *testing.T) {
	var s Set
	for _, i := range []int{1, 5, 64, 200} {
		s.Add(i)
	}
	if !s.Has(64) || !s.Has(200) || s.Has(2) || s.Has(1000) {
		t.Fatal("membership wrong")
	}
	if s.Len() != 4 {
		t.Fatalf("Len = %d, want 4", s.Len())
	}

	s.Remove(64)
	if s.Has(64) || s.Len() != 3 {
		t.Fatal("remove failed")
	}

	var o Set
	o.Add(2)
	o.Add(300)
	s.Union(&o)
	if !s.Has(2) || !s.Has(300) || s.Len() != 5 {
		t.Fatalf("union wrong, Len = %d", s.Len())
	}
}

=== RUN   TestSet
--- PASS: TestSet (0.00s)
PASS
ok  	example.test/lab	1.243s

The word index is i / 64 and the bit within it is i % 64, and the Go compiler turns the division and modulus by 64 into a shift and a mask. The zero value is an empty set, following the zero value rule. The test exercises add, test, count, remove and union, including a membership query beyond the stored words, which must return false and not panic. The memory is max/8 bytes, so a set whose largest member is a million costs about 125 KB, which is a poor deal for sparse sets and a good one for dense ones.

Bytes in order: endianness

When a number crosses a byte boundary, as in a file format or a network packet, the order of its bytes matters. Big-endian puts the most significant byte first, and network protocols use it. Little-endian puts the least significant byte first, and x86 and most ARM systems use it in memory. The encoding/binary package does the shifting and masking for you, and writing it out shows the difference:

package main

import (
	"encoding/binary"
	"fmt"
)

func main() {
	buf := make([]byte, 4)

	binary.BigEndian.PutUint32(buf, 0x01020304)
	fmt.Printf("big:    % x -> %#x\n", buf, binary.BigEndian.Uint32(buf))

	binary.LittleEndian.PutUint32(buf, 0x01020304)
	fmt.Printf("little: % x -> %#x\n", buf, binary.LittleEndian.Uint32(buf))

	fmt.Printf("misread: %#x\n", binary.BigEndian.Uint32(buf))
	fmt.Println(binary.BigEndian.Uint16([]byte{0x01, 0x00}), binary.LittleEndian.Uint16([]byte{0x01, 0x00}))
}

big:    01 02 03 04 -> 0x1020304
little: 04 03 02 01 -> 0x1020304
misread: 0x4030201
256 1

The same number lays out as 01 02 03 04 in one order and 04 03 02 01 in the other. Reading little-endian bytes as big-endian gives 0x4030201, which is the typical symptom of a byte order mistake: values that are plausible but wrong. The two-byte case at the end gives 256 and 1 for the same two bytes. Always decide the order from the format's specification and never from your own machine, and never reinterpret raw memory with unsafe to get an integer, since the result changes with the CPU. For streams, binary.Read and binary.Write handle whole structs, with the same explicit order argument.

Two small algorithms

Parity, whether the number of set bits is odd, is one line with math/bits: bits.OnesCount(x) & 1. It is used in checksums and error detection. A Gray code is a sequence where consecutive values differ in a single bit, and it is x ^ (x >> 1):

package main

import (
	"fmt"
	"math/bits"
)

func main() {
	for i := range uint(8) {
		gray := i ^ (i >> 1)
		fmt.Printf("%d  %03b  gray %03b  parity %d\n", i, i, gray, bits.OnesCount(i)&1)
	}
}

0  000  gray 000  parity 0
1  001  gray 001  parity 1
2  010  gray 011  parity 1
3  011  gray 010  parity 0
4  100  gray 110  parity 1
5  101  gray 111  parity 0
6  110  gray 101  parity 0
7  111  gray 100  parity 1

Read the gray column down: 000, 001, 011, 010, 110, 111, 101, 100, and every step flips exactly one bit. That property makes Gray codes useful for rotary encoders and for reducing glitches when a counter is read while it changes. Neither algorithm is something you will write every week, and both show how much the operators do in a line once you know the identities.

Permissions are bits

The most familiar bit field to anyone who has used a Unix shell is the file mode, and Go's fs.FileMode is exactly that, with a String method that prints it the way ls does:

package main

import (
	"fmt"
	"io/fs"
)

func main() {
	mode := fs.FileMode(0o754)
	fmt.Println(mode, mode.Perm()&0o200 != 0, mode&0o001 != 0)

	mode &^= 0o040
	mode |= 0o001
	fmt.Println(mode, fs.ModeDir|0o755)
}

-rwxr-xr-- true false
-rwx--xr-x drwxr-xr-x

Octal digits map to the three permission groups, so 0o754 is rwxr-xr--. The test mode&0o001 != 0 asks whether the "others execute" bit is set, which it is not, and &^= 0o040 clears group read while |= 0o001 adds others execute. The fs.ModeDir flag lives in the high bits of the same value, so ModeDir|0o755 prints as drwxr-xr-x. The same arithmetic with named constants is what reading and writing files used for the permission argument.

Pinning "any" against "all" with a test

The flag methods earlier hide a trap that deserves a test: testing a combined mask with & and != 0 answers "is any of these set", and what you often mean is "are all of these set". Writing both as methods and testing them side by side keeps the two meanings apart:

package perm

type Perm uint8

const (
	Read Perm = 1 << iota
	Write
	Exec
)

func (p Perm) HasAny(m Perm) bool { return p&m != 0 }
func (p Perm) HasAll(m Perm) bool { return p&m == m }

package perm

import "testing"

func TestAnyAll(t *testing.T) {
	cases := []struct {
		name     string
		have     Perm
		want     Perm
		any, all bool
	}{
		{"exact", Read | Write, Read | Write, true, true},
		{"subset", Read | Write | Exec, Read | Write, true, true},
		{"overlap", Read, Read | Write, true, false},
		{"disjoint", Exec, Read | Write, false, false},
		{"empty mask", Read, 0, false, true},
	}
	for _, c := range cases {
		t.Run(c.name, func(t *testing.T) {
			if got := c.have.HasAny(c.want); got != c.any {
				t.Errorf("HasAny = %v, want %v", got, c.any)
			}
			if got := c.have.HasAll(c.want); got != c.all {
				t.Errorf("HasAll = %v, want %v", got, c.all)
			}
		})
	}
}

=== RUN   TestAnyAll
=== RUN   TestAnyAll/exact
=== RUN   TestAnyAll/subset
=== RUN   TestAnyAll/overlap
=== RUN   TestAnyAll/disjoint
=== RUN   TestAnyAll/empty_mask
--- PASS: TestAnyAll (0.00s)
    --- PASS: TestAnyAll/exact (0.00s)
    --- PASS: TestAnyAll/subset (0.00s)
    --- PASS: TestAnyAll/overlap (0.00s)
    --- PASS: TestAnyAll/disjoint (0.00s)
    --- PASS: TestAnyAll/empty_mask (0.00s)
PASS
ok  	example.test/lab	1.229s

The overlap row is the one that separates them: Read against Read|Write is "any" but not "all". The empty mask row is the edge people forget. With no bits asked for, "any" is false, since nothing matches, and "all" is true, since there is nothing missing, and your authorization code should decide which of those it wants before it hits one in production. A table like this takes five minutes and prevents a class of access bugs that review often misses.

A hash function as bit arithmetic

Hash functions are mostly xors, shifts and multiplications that rely on wraparound, the one place where the overflow in integer overflow is the intended behavior. FNV-1a, a simple hash for short keys, is two lines per byte, and it matches the standard library's implementation:

package main

import (
	"fmt"
	"hash/fnv"
)

func fnv1a(s string) uint32 {
	h := uint32(2166136261)
	for i := 0; i < len(s); i++ {
		h ^= uint32(s[i])
		h *= 16777619
	}
	return h
}

func main() {
	std := fnv.New32a()
	std.Write([]byte("gohacks"))

	fmt.Printf("%#x %#x %t\n", fnv1a("gohacks"), std.Sum32(), fnv1a("gohacks") == std.Sum32())
}

0x14fd9f87 0x14fd9f87 true

The multiplication overflows on nearly every byte, and the result is deterministic because unsigned arithmetic wraps. FNV is not suitable where an attacker chooses the input, since collisions are easy to find, and it is a fine bucket selector for in-process tables. If you copy a hash like this into your own code, add a comment saying the wraparound is deliberate, so that nobody adds an overflow check.

Shift mistakes

Three mistakes account for most shift bugs. Shifting by a count that is not a constant is allowed, and a count of the type's width or more produces zero for unsigned values, not a wrapped shift as in C:

package main

import "fmt"

func main() {
	var x uint32 = 1
	n := 40
	fmt.Println(x<<n, x<<(n-9))

	neg := -1
	fmt.Println(x << neg)
}

0 2147483648
panic: runtime error: negative shift amount

...

The first print gives 0 and 2147483648: shifting a 32-bit value by 40 bits shifted everything out, and shifting by 31 left a single bit in the top position. The second shift uses a negative count, which is legal to write and panics at run time with negative shift amount. If the count comes from input, check it first, and use an unsigned count type to rule the panic out. The third classic is mixing up precedence: a & b == c parses as a & (b == c) in C, and Go fixed it by giving & the multiplication precedence, so a&b == c means what it says, but writing parentheses around bit expressions is still a kindness to the reader.

When bit tricks are the wrong tool

A packed integer is hard to read and hard to change. If a value has more than a handful of fields and no performance reason to be compact, a struct with named fields is clearer, and the compiler packs bools into a struct the way it likes. Bit flags are right for a fixed small set that is stored or sent, such as permissions, options to a function and wire formats. A bitset beats a map for dense integer sets and loses for sparse ones. And when you only need to count or find bits, reach for math/bits before a loop. The operators are defined in the specification's arithmetic section, and the math/bits documentation lists every function with its intended use.