Go Guide

DP, math & design · Lesson 40 of 62 · about 40 min

Bit manipulation

Work directly with the binary representation: the operators, the handful of tricks worth memorizing, math/bits, and bitmasks as sets.

pkg.go.dev: math/bits ↗Go spec: arithmetic operators ↗
On this page · 13 sections
  1. 01Binary in one minute
  2. 02The operators
  3. 03Tricks worth memorizing
  4. 04XOR: things that cancel
  5. 05math/bits
  6. 06Bitmasks as sets
  7. 07Signed vs unsigned shifts
  8. 08The full program
  9. 09Complexity
  10. 10Recognizing the pattern
  11. 11Summary
  12. 12Check your understanding
  13. 13Practice in Go

Binary in one minute#

13 in binary is 1101: 8 + 4 + 0 + 1. Bit positions count from the right starting at 0, so bits 0, 2 and 3 are set. In Go you can write binary literals (0b1101) and print binary with fmt.Printf("%b", x) or %08b for a fixed width.

The operators#

OperatorNameRule per bit12 op 10 (1100, 1010)
&AND1 if both are 11000 = 8
|OR1 if either is 11110 = 14
^XOR1 if they differ0110 = 6
&^AND NOT (Go only)1 if left is 1 and right is 00100 = 4
<<left shiftmove bits left, fill with 012 << 1 = 24
>>right shiftmove bits right12 >> 2 = 3

Shifting left by k multiplies by 2ᵏ; shifting right divides by 2ᵏ (rounding down for non-negative numbers). Unary ^x flips every bit.

Try it

%04b prints a number as 4 binary digits, which makes every operator easy to check by eye:

operators.go
Go
package main
 
import "fmt"
 
func main() {
	a, b := 12, 10
	fmt.Printf("a      %04b (%d)\n", a, a)
	fmt.Printf("b      %04b (%d)\n", b, b)
	fmt.Printf("a & b  %04b (%d)\n", a&b, a&b)
	fmt.Printf("a | b  %04b (%d)\n", a|b, a|b)
	fmt.Printf("a ^ b  %04b (%d)\n", a^b, a^b)
	fmt.Printf("a &^ b %04b (%d)\n", a&^b, a&^b)
	fmt.Printf("a << 1 %05b (%d)\n", a<<1, a<<1)
	fmt.Printf("a >> 2 %04b (%d)\n", a>>2, a>>2)
	fmt.Println(0b1101, 0x0F, 1<<10) // binary, hex and shift literals
}
Output
a      1100 (12)
b      1010 (10)
a & b  1000 (8)
a | b  1110 (14)
a ^ b  0110 (6)
a &^ b 0100 (4)
a << 1 11000 (24)
a >> 2 0011 (3)
13 15 1024

Tricks worth memorizing#

ExpressionMeaningExample (x = 12 = 1100)
x & 1is x odd?0
x & (1 << i) != 0is bit i set?i = 2: true
x | (1 << i)set bit ii = 0: 1101
x &^ (1 << i)clear bit ii = 3: 0100
x ^ (1 << i)toggle bit ii = 1: 1110
x & (x - 1)clear the lowest set bit1000
x & -xkeep only the lowest set bit0100
x > 0 && x&(x-1) == 0is x a power of two?false

Why x & (x-1) works: subtracting 1 turns the lowest 1 into 0 and every 0 below it into 1. AND with the original keeps everything above and wipes out that region.

binary
x = 121100
x - 1 = 111011
x & (x-1)1000

Try it

Each trick from the table, applied to 12:

tricks.go
Go
package main
 
import "fmt"
 
func main() {
	x := 12 // 1100
	fmt.Printf("x            %04b\n", x)
	fmt.Printf("odd?         %v\n", x&1 == 1)
	fmt.Printf("bit 2 set?   %v\n", x&(1<<2) != 0)
	fmt.Printf("set bit 0    %04b\n", x|1<<0)
	fmt.Printf("clear bit 3  %04b\n", x&^(1<<3))
	fmt.Printf("toggle bit 1 %04b\n", x^(1<<1))
	fmt.Printf("x & (x-1)    %04b  lowest 1 cleared\n", x&(x-1))
	fmt.Printf("x & -x       %04b  lowest 1 kept\n", x&-x)
 
	fmt.Print("powers of two up to 70:")
	for n := 1; n <= 70; n++ {
		if n&(n-1) == 0 {
			fmt.Print(" ", n)
		}
	}
	fmt.Println()
 
	// Count set bits by clearing the lowest one until nothing is left.
	n, count := 0b1011_0110, 0
	for v := n; v != 0; v &= v - 1 {
		count++
	}
	fmt.Printf("%b has %d set bits\n", n, count)
}
Output
x            1100
odd?         false
bit 2 set?   true
set bit 0    1101
clear bit 3  0100
toggle bit 1 1110
x & (x-1)    1000  lowest 1 cleared
x & -x       0100  lowest 1 kept
powers of two up to 70: 1 2 4 8 16 32 64
10110110 has 5 set bits

XOR: things that cancel#

XOR has three properties: x ^ x = 0, x ^ 0 = x, and order does not matter. So XOR-ing a list where every value appears twice except one leaves exactly that one:

4 ^ 1 ^ 2 ^ 1 ^ 2  =  4 ^ (1 ^ 1) ^ (2 ^ 2)  =  4 ^ 0 ^ 0  =  4

Run the trace

xor_trace.go
Go
package main
 
import "fmt"
 
func main() {
	nums := []int{4, 1, 2, 1, 2}
	acc := 0
	for _, n := range nums {
		acc ^= n
		fmt.Printf("^ %d (%03b) -> acc = %03b (%d)\n", n, n, acc, acc)
	}
	fmt.Println("appears once:", acc)
 
	// Missing number: XOR all indexes 0..n with all values; every present number cancels.
	vals := []int{3, 0, 1} // 0..3 with one missing
	miss := len(vals)
	for i, v := range vals {
		miss ^= i ^ v
	}
	fmt.Println("missing from", vals, "is", miss)
}
Output
^ 4 (100) -> acc = 100 (4)
^ 1 (001) -> acc = 101 (5)
^ 2 (010) -> acc = 111 (7)
^ 1 (001) -> acc = 110 (6)
^ 2 (010) -> acc = 100 (4)
appears once: 4
missing from [3 0 1] is 2

The accumulator jumps around in the middle, but each pair cancels the moment its second copy arrives.

math/bits#

The math/bits package maps to fast CPU instructions on most machines:

FunctionReturns
bits.OnesCount(x)number of set bits (population count)
bits.TrailingZeros(x)index of the lowest set bit
bits.Len(x)bits needed to represent x (position of highest set bit + 1)
bits.Reverse32(x)the bits in reverse order

Try it

mathbits.go
Go
package main
 
import (
	"fmt"
	"math/bits"
)
 
func main() {
	var x uint = 0b1011_0000
	fmt.Printf("x = %b\n", x)
	fmt.Println("OnesCount:    ", bits.OnesCount(x))
	fmt.Println("TrailingZeros:", bits.TrailingZeros(x))
	fmt.Println("Len:          ", bits.Len(x))
	fmt.Printf("Reverse8:      %08b\n", bits.Reverse8(uint8(x)))
	fmt.Println("Len(1000) =", bits.Len(1000), "so 1000 needs 10 bits")
}
Output
x = 10110000
OnesCount:     3
TrailingZeros: 4
Len:           8
Reverse8:      00001101
Len(1000) = 10 so 1000 needs 10 bits

Bitmasks as sets#

An int can represent any subset of up to 64 items: bit i set means item i is in the set. Union is |, intersection is &, difference is &^, and size is bits.OnesCount. To enumerate every subset of n items, count from 0 to 2ⁿ - 1: each number is one subset. This powers bitmask DP (traveling salesman on small n, assigning tasks to workers), where the state "which items are used" fits in one integer.

Try it: a set of skills in one integer

Each skill gets a bit position. Set operations become single operators:

bitmask_set.go
Go
package main
 
import (
	"fmt"
	"math/bits"
	"strings"
)
 
var names = []string{"go", "sql", "docker", "rust", "react"}
 
func show(set uint) string {
	var out []string
	for i, n := range names {
		if set&(1<<i) != 0 {
			out = append(out, n)
		}
	}
	return "{" + strings.Join(out, " ") + "}"
}
 
func main() {
	ana := uint(1<<0 | 1<<1 | 1<<2) // go, sql, docker
	bo := uint(1<<0 | 1<<3)         // go, rust
	fmt.Printf("ana   %05b %s\n", ana, show(ana))
	fmt.Printf("bo    %05b %s\n", bo, show(bo))
	fmt.Printf("both  %05b %s\n", ana&bo, show(ana&bo))
	fmt.Printf("any   %05b %s\n", ana|bo, show(ana|bo))
	fmt.Printf("diff  %05b %s\n", ana&^bo, show(ana&^bo))
	fmt.Println("team covers", bits.OnesCount(ana|bo), "of", len(names), "skills")
 
	// Every subset of the first 3 skills: count from 0 to 2^3 - 1.
	for mask := uint(0); mask < 1<<3; mask++ {
		fmt.Printf("%03b %s\n", mask, show(mask))
	}
}
Output
ana   00111 {go sql docker}
bo    01001 {go rust}
both  00001 {go}
any   01111 {go sql docker rust}
diff  00110 {sql docker}
team covers 4 of 5 skills
000 {}
001 {go}
010 {sql}
011 {go sql}
100 {docker}
101 {go docker}
110 {sql docker}
111 {go sql docker}

Signed vs unsigned shifts#

Right-shifting a negative signed integer keeps the sign (arithmetic shift): -8 >> 1 is -4. For raw bit work, use unsigned types (uint, uint32, uint64) so shifts behave as plain bit movement.

Try it

shifts.go
Go
package main
 
import "fmt"
 
func main() {
	var s int8 = -8
	var u uint8 = 0b1111_1000 // the same bits as -8 in an int8
	fmt.Printf("signed   %d >> 1 = %d\n", s, s>>1)
	fmt.Printf("unsigned %08b >> 1 = %08b (%d)\n", u, u>>1, u>>1)
	fmt.Printf("^uint8(0) = %08b (%d)\n", ^uint8(0), ^uint8(0))
}
Output
signed   -8 >> 1 = -4
unsigned 11111000 >> 1 = 01111100 (124)
^uint8(0) = 11111111 (255)

The signed shift copies the sign bit into the top, keeping the number negative; the unsigned shift fills with 0.

The full program#

bits.go
Go
package main
 
import (
	"fmt"
	"math/bits"
)
 
func singleNumber(nums []int) int {
	res := 0
	for _, n := range nums {
		res ^= n
	}
	return res
}
 
func countBits(n int) []int {
	ans := make([]int, n+1)
	for i := 1; i <= n; i++ {
		ans[i] = ans[i&(i-1)] + 1 // i with its lowest bit cleared, plus that bit
	}
	return ans
}
 
func missingNumber(nums []int) int {
	x := len(nums)
	for i, n := range nums {
		x ^= i ^ n
	}
	return x
}
 
func isPowerOfTwo(x int) bool { return x > 0 && x&(x-1) == 0 }
 
func allSubsets(items []string) [][]string {
	n := len(items)
	var res [][]string
	for mask := 0; mask < 1<<n; mask++ {
		var sub []string
		for i := range n {
			if mask&(1<<i) != 0 {
				sub = append(sub, items[i])
			}
		}
		res = append(res, sub)
	}
	return res
}
 
func main() {
	x := 12
	fmt.Printf("%04b %04b %04b %04b\n", x&10, x|10, x^10, x&^10)
	fmt.Println(x<<1, x>>2, x&1 == 1, x&(1<<2) != 0)
	fmt.Printf("%04b %04b\n", x&(x-1), x&-x)
 
	fmt.Println(singleNumber([]int{4, 1, 2, 1, 2}), missingNumber([]int{3, 0, 1}))
	fmt.Println(countBits(5))
	fmt.Println(isPowerOfTwo(64), isPowerOfTwo(12), isPowerOfTwo(0))
 
	var u uint32 = 0b1011
	fmt.Println(bits.OnesCount32(u), bits.TrailingZeros32(8), bits.Len(255))
 
	fmt.Println(allSubsets([]string{"a", "b", "c"}))
 
	var set uint64
	for _, item := range []int{1, 5, 9} {
		set |= 1 << item
	}
	other := uint64(1<<5 | 1<<7)
	fmt.Println(bits.OnesCount64(set), bits.OnesCount64(set&other), set&^other == 1<<1|1<<9)
}
Output
1000 1110 0110 0100
24 3 false true
1000 0100
4 2
[0 1 1 2 1 2]
true false false
3 3 8
[[] [a] [b] [a b] [c] [a c] [b c] [a b c]]
3 1 true

Complexity#

OperationTime
any single bit operation, math/bits functionO(1)
XOR scan (single number, missing number)O(n), O(1) space
count bits 0..nO(n)
enumerate all subsetsO(n · 2ⁿ)

Recognizing the pattern#

"Appears once / twice", "missing number", "power of two", "count set bits", constraints like n ≤ 20 with "all subsets" (bitmask enumeration or bitmask DP), and anything asking for O(1) extra space where values cancel.

Summary#

  • &, |, ^, &^, <<, >> work on all bits at once.
  • x & (x-1) clears the lowest set bit; x & -x isolates it.
  • XOR cancels pairs: single number, missing number.
  • math/bits gives fast counting and searching of bits.
  • An integer can be a set of up to 64 items; counting 0..2ⁿ-1 enumerates all subsets.

Check your understanding

Answer before scrolling back up. If you miss one, reread the matching section, then try again.

  1. Q1.x & (x - 1) does what?

  2. Q2.Why does XOR-ing all numbers find the single number in [4, 1, 2, 1, 2]?

  3. Q3.What does Go's &^ operator do?

  4. Q4.How do you check whether bit i is set in mask?

Practice in Go

Write a table test first, then the solution. On LeetCode, choose Go as the language. Open a hint only after 15 minutes stuck.

Finished this lesson?

Mark it done to track your progress. It is saved in this browser only.