August 27, 2018

Efficiently Checking if a Number Has Two Consecutive Bits Set

Last week someone I mentor asked for help with a programming challenge that involved some bit twiddling. The first part of the problem was

A number is known as special bit number if its binary representation contains atleast two consecutive 1’s or set bits. For example 7 wih binary representation 111 is a special bit number. Similarly 3 (11) is also a special bit number.

The naive implementation was quite simple but got me thinking if there were better options.

1. Right Shift and Counter

This is the most straightforward approach where we check the least significant bit (LSB) and increment a counter if it is 1. As soon as the counter hits 2 we exit or reset to 0 if the bit is not set.

func isSpecial(n uint32) bool {
	for wasLastBitOne := false; n > 0; n = n >> 1 {
		isCurrentBitOne := n%2 == 1
		if isCurrentBitOne && wasLastBitOne {
			return true
		}
		wasLastBitOne = isCurrentBitOne
	}

	return false
}

Now let’s write a quick benchmark to see how it performs.

func BenchmarkIsSpecial(b *testing.B) {
	for n := 0; n < b.N; n++ {
		isSpecial(uint32(n))
	}
}

And the results are: you can perform about a 100 million of these per second.

> go test -bench 'BenchmarkIsSpecial$'
goos: darwin
goarch: amd64
pkg: github.com/zqureshi/special
BenchmarkIsSpecial-8    200000000          9.46 ns/op
PASS
ok    github.com/zqureshi/special 2.861s

2. Speedup via Lookup Table

We are working with 32-bit unsigned integers and notice that checking an 8-bit long subsequence is no different than checking the whole number. For an 8-bit sequence we have 256 (2**8) possible combinations and can precompute a lookup table of all possible results.

var lookupTable = [256]bool{}

func init() {
	fmt.Println("Recomputing lookup table...")
	for i := uint32(0); i < 256; i++ {
		lookupTable[i] = isSpecial(i)
	}
}

func isSpecialLookup(n uint32) bool {
	if lookupTable[3] == false {
		panic("Lookup table not initialized!")
	}

	return lookupTable[uint8(n)] ||
		lookupTable[uint8(n>>7)] ||
		lookupTable[uint8(n>>14)] ||
		lookupTable[uint8(n>>21)] ||
		lookupTable[uint8(n>>24)]
}

An interesting thing to note here is that we cannot just check four bit ranges 0-7, 8-15, 16-23, 28-31 because we will miss numbers that have consecutive bits on the boundary i.e. bit 7 and 8, therefore we must always check overlapping ranges 0-7, 7-14, 14-21, 21-28, 24-31. In the last comparison of bits 24-31 we re-check bits 24-28 but it is easier to just do so than special case it and add extra logic.

And now let’s also benchmark this.

func BenchmarkIsSpecialLookup(b *testing.B) {
	for n := 0; n < b.N; n++ {
		isSpecialLookup(uint32(n))
	}
}
> go test -bench '.'
Recomputing lookup table...
goos: darwin
goarch: amd64
pkg: github.com/zqureshi/special
BenchmarkIsSpecial-8          200000000          9.85 ns/op
BenchmarkIsSpecialLookup-8    1000000000         2.60 ns/op
PASS
ok    github.com/zqureshi/special 5.817s

We get an almost 4x speedup using this approach as we are doing lesser comparisons and memory writes but also due to the fact that the whole lookup table fits in 32 bytes of memory which sits cosily in a 64 byte cache line.

3. Larger Lookup Table

We could extend the previous approach and precompute 65536 (2**16) values which would allow us to cover the whole number in just 3 comparisons 0-15, 15-30, 16-31.

func isSpecialLookup16(n uint32) bool {
	if lookupTable[3] == false {
		panic("Lookup table not initialized!")
	}

	return lookupTable[uint16(n)] ||
		lookupTable[uint16(n>>15)] ||
		lookupTable[uint16(n>>16)]
}

And benchmark

func BenchmarkIsSpecialLookup16(b *testing.B) {
	for n := 0; n < b.N; n++ {
		isSpecialLookup16(uint32(n))
	}
}
Recomputing lookup table...
goos: darwin
goarch: amd64
pkg: github.com/zqureshi/special
BenchmarkIsSpecial-8            200000000          9.57 ns/op
BenchmarkIsSpecialLookup-8      1000000000         2.62 ns/op
BenchmarkIsSpecialLookup16-8    1000000000         2.31 ns/op
PASS
ok    github.com/zqureshi/special 8.325s

A 12% improvement in runtime but a 256x blowup in table size (32 bytes vs 8192 bytes). While this performs better in this synthetic benchmark it might not perform as well in production because of cache line and page misses.

4. Finding Something Better

At this point I was quite happy with the progress but was wondering if there was some intrinsic property of numbers that could be exploited to make this even faster. I landed upon this HackerRank post and a collection of bit twiddling hacks from Stanford’s graphics department.

The solution was quite ingenious, if you take any binary number it will have runs of set bits followed by one or more unset bits. Now if you left shift the number, you move the 0 left and now if you bitwise and it with the original number you have effectively cleared one set bit from a run. If you repeat this process you will clear another bit, and another until the number is 0.

A worked out example will demonstrate this better.

14      =   1110
14 << 1 =  11100
a & b   =  01100

12      =   1100
12 << 1 =  11000
a & b   =  01000

8       =   1000
8  << 1 =  10000
a & b   =  00000

We can then simplify this algorithm to derive that if a number has at least two consecutive bits set, then left shift followed by bitwise and will result in a non-zero value. Let’s work through this.

12      =   1100
12 << 1 =  11000
a & b   =  01000

10      =   1010
10 << 1 =  10100
a & b   =  00000

So now the code simply becomes

func isSpecialLeftShift(n uint32) bool {
	return (n & (n << 1)) > 0
}

and benchmark

func BenchmarkIsSpecialLeftShift(b *testing.B) {
	for n := 0; n < b.N; n++ {
		isSpecialLeftShift(uint32(n))
	}
}
Recomputing lookup table...
goos: darwin
goarch: amd64
pkg: github.com/zqureshi/special
BenchmarkIsSpecial-8              200000000          9.55 ns/op
BenchmarkIsSpecialLookup-8        1000000000         2.60 ns/op
BenchmarkIsSpecialLookup16-8      1000000000         2.32 ns/op
BenchmarkIsSpecialLeftShift-8     2000000000         0.27 ns/op
PASS
ok    github.com/zqureshi/special 8.871s

This is a 35x improvement over our naive approach and only involves 3 instructions, which means it is also a candidate for inlining.

5. Epilogue

One thing that we didn’t talk about was how did I verify that my implementations were correct? I implemented the naive version and manually tested it on various inputs. Then for every other implementation I iterated through the first billion integers and reconciled the optimized against the naive.

func main() {
	for n := uint32(0); n < 1000000000; n++ {
		result := isSpecial(n)
		if isSpecialLookup(n) != result {
			fmt.Printf("Error: %v == %b isSpecial: %v, isSpecialLookup: %v\n", n, n, result, isSpecialLookup(n))
			break
		}
		if isSpecialLookup16(n) != result {
			fmt.Printf("Error: %v == %b isSpecial: %v, isSpecialLookup16: %v\n", n, n, result, isSpecialLookup16(n))
			break
		}
		if isSpecialLeftShift(n) != result {
			fmt.Printf("Error: %v == %b isSpecial: %v, isSpecialLeftShift: %v\n", n, n, result, isSpecialLeftShift(n))
			break
		}
	}
}