I’m hacking around with platformer mechanics in Ebitengine, a minimalist 2D game engine for Go. A friend recently asked me about the bitmasks I was using in the sourcecode for collision detection, so here’s a quick write-up.

Bitmasks

A unsigned 16-bit integer is declared like this.

var foo uint16   // 0000 0000 0000 0000

The comment shows the associated (stack) memory, in half-byte chunks. We can treat a uint16 as a compact bundle of 16 boolean values.

Binary constants

We can declare foo explicitly by using the fact that any constant value starting with 0b in Go represents a binary integer.

var foo uint16 = 0b1100_1001_0110_0011

Go allows us to include the underscores to make large constant values easier to read. They’re ignored by the parser.

Printing in binary

fmt.Printf allows us to examine the binary contents of any integer using the "%b" formatting flag:

fmt.Printf("%b", 0b1011_1001) // prints "10111001"

Setting values

To set the nth value, (indexed from 0 to 15):

foo = foo | (1 << n)

That << is the “left-shift” bit operator. x << y pads the binary representation of x with y zeroes on the right, truncating any leftovers to fit in the available storage. For example:

0b1110110 << 4 == 0b01100000

The | operator is bitwise boolean ‘OR’. It combines two integers by lining their binary representation up into columns and ORing their contents. If we were in elementary school, we might do it “on paper” like below:

    1100 0011 0110 0101
 |  0000 0100 1111 0110
-----------------------  
    1100 0111 1111 0111

Putting the expression foo | (1<<n) together, we can see that (1<<n) constructs a value whose nth bit is set. ORing that value with foo sets the nth bit.

Testing values

How do we test whether the nth bit in a bitvector has been set? We can use boolean AND and compare the result to zero.

if foo & (1 << n) > 0 {
  fmt.Println("bit %d is set", n)
}

Similarly to |, the & operator acts bitwise on integers as if each of their aligned pairs of bits were boolean values.

    1100 0011 0110 0101
 &  0000 0100 1111 0110
-----------------------  
    0000 0000 0110 0100

Since (1<<n) is a value with only one bit set (the nth bit), ANDing that expression with foo will only yield a non-zero value if the nth bit of foo is non-zero.

Unsetting values

Without mucking around with sign bits and two’s complement, I will just tell you that the following expression can be used to unset the nth bit.

foo = foo - (1<<n)

The reason this works involves sign bits and carrying, but you can see it in action for yourself.

fmt.Printf("%.8b", byte(0b00001011 - (1<<3))) // prints "00000011"  -- %.8b" left pads with zeroes up to 8 bits

Testing multiple values at once

It’s not too hard to see how to set multiple values at once. If we set up some consts, we can use this to cheaply pass around small cardinality sets.

type SetOfThings uint8

const (
  Nothing SetOfThings = 0
  First = 1    // 0b0000_0001
  Second = 2   // 0b0000_0010
  Third = 4    // 0b0000_0100
  Fourth = 8   // 0b0000_1000
)

Then the set containing the first and third things is First|Third. We can check if a set contains the Second thing using set&Second > 0, remove the Third thing with set = set-Third, and add the First thing with set = set|First.

In fact, we can use iota to manage the const block for us, instead of making everything so explicit. The constants in the below block are identical to the ones above.

const (
  Nothing SetOfThings = 0
  First = 1 << (iota-1)
  Second
  Third
  Fourth
)

The advantage of bitmasks over sets is that they can be tested cheaply in the CPU without accessing heap memory. The disadvantage is they only work for small cardinality sets. For large cardinality sets we can use a bitvector.

Bitvectors

A bitvector is just a []byte which is treated like a large contiguous bitmask.

To access the nth bit, we first integer-divide 8 to find the correct byte, then take the modulus by 8 to find the location of the bit within the byte we found.

func Bitn(bitvector []byte, n int) bool { // returns true if bit n is set; false otherwise.
    return bitvector[n/8] & (1<<(n%8)) > 0
}

Here’s an example for a bitvector with 40 bits. I’ve printed each byte in binary. If we’re looking for the 23rd bit, we go to the 2nd index (23/8 = 2), and look at the 7th bit (23%8 == 7)

  index 0     index 1    index 2    index 3    index 4                        
[ 0000_0000, 0100_0010, 0000_1000, 0101_0000, 0110_0000 ]
                        ^--- 7th bit (0-indexed)

WARNING: The above function panics if the bitvector isn’t large enough to index with its argument. This is easily fixed.

With access in order, the rest of the code is simple, building on what we already know about bitmasks.

Setting values

Setting values is just the correct combination of bitvector access and the corresponding bitmask operation.

func Bitset(bitvector []byte, n int) {
    bitvector[n/8] |= (1<<(n%8))    // |= is 'bitwise or equals', analogous to +=
}

Unsetting values

The same goes for unsetting values, combining access and the correct bitmask operation from above.

func Bitunset(bitvector []byte, n int) {
    bitvector[n/8] -= (1<<(n%8))
}

Equality checks

Testing whether the entirety of one bitvector is equal to another is simple: use the standard library: bytes.Equal does exactly this.

Conclusion

Other operations are possible, but setting, unsetting, and testing are usually all that you need, if you need it. When storing and comparing massive amounts of booleans, bitvectors can provide a significant space savings over a []bool, but as always, you should consider your use case carefully and evaluate whether the added complexity is worth the benefits.

For more advanced bit-twiddling hacks, check out Sean Eron Anderson’s Website at Stanford.