Skew Binary

Remember my earlier post about balanced ternary? Well, another odd numbering system has been in the news recently.

Randall Munroe just published a collection of XKCD comics. The page numbers start out like this:

1, 2, 10, 11, 12, 20, 100, 101, 102, …

This had a lot of people trying to guess what the numbering system is. It’s obviously not binary, because it has ‘2’s in it. It looks a lot like ternary, but that would go like this:

1, 2, 10, 11, 12, 20, 21, 22, 100, 101, …

It turns out it is something called skew binary. In skew binary, the nth digit represents a multiple of (2^n-1). Because of the “missing value” in the radix, you need more digits than just the 0 and 1 which binary uses. But interestingly, it turns out that you only need to use 2 per value. You’ll never see something like 22.

Here are some examples:

1 = 1*(2^1-1) = 1*1 = 1
2 = 2*(2^1-1) = 2*1 = 2
10 = 1*(2^2-1) + 0*(1-1) = 1*3 + 0*1 = 3
11 = 1*(2^2-1) + 1*(1-1) = 1*3 + 1*1 = 4
...
101 = 1*(2^3-1) + 0*(2^2-1) + 1*(2^1-1) = 1*7 + 0*3 + 1*1 = 8
102 = 1*(2^3-1) + 0*(2^2-1) + 2*(2^1-1) = 1*7 + 0*3 + 2*1 = 9

Make sense?

If you count in skew binary, you’ll see an interesting pattern where that 2 keeps appearing on the right and sweeping left through all of the digits and then disappearing again. That’s related to one of the more interesting properties of skew binary. When you’re adding, there is at most a single carry, as discussed here. That’s a useful property if you’re implementing an adder. It might also make for an interesting looking clock.

For more on this, go check out Morton Barklund’s blog.