A Quick 'n Dirty Color Sequence
August 29th, 2011

Maybe you've got a list of things, like friends or appointments or map locations, and you want to give each one its own color so the user can distinguish them easily. The user can make new friends or appointments, so you don't know ahead of time how many colors you'll need. And when the user adds a new item, you want its color to be as different from all other colors as possible, to avoid confusion. How do you decide on the sequence of colors to give each item? And can it be a random-access sequence? It sounds tricky, maybe like some linear optimization problem, but in fact there's a marvelously simple and surprising solution.

We can think of colors in terms of hue, saturation, and lightness. Since these colors are going to be presented next to each other, they have to look good together - no bright colors mixing with dark ones, for example - so the color choices will vary only in hue. That way blues, greens, reds, etc. will all be represented, but they'll all be equally bright and equally saturated.

So let's try to pick some hues on the edge of the color wheel. We want the colors to be maximally different, so each time we add a new hue, we'll try to put it as far away from all the others as we can. The first color can be anything, so let's start with red. The second color then has to go opposite it.

1 2

The third color needs to be as far away as possible from the first two, which means either the top or bottom. The fourth color then must take bottom or top.

1 2 3 4

I get it, we just keep on bisecting!

1 2 3 4 5 6 7 8

See a pattern yet? Maybe if we write it out as a list of rotations:

$0$, $\frac 1 2$, $\frac 1 4$, $\frac 3 4$, $\frac 1 8$, $\frac 5 8$, $\frac 3 8$, $\frac 7 8$ …

It's easy to continue this series, but it's not obvious how to compute, say, the 100th element. But what if...what if we write it like this (read top to bottom, left to right):

$0 = \frac 0 2 + \frac 0 4 + \frac 0 8$
$\frac 1 2 = \frac 1 2 + \frac 0 4 + \frac 0 8$
$\frac 1 4 = \frac 0 2 + \frac 1 4 + \frac 0 8$
$\frac 3 4 = \frac 1 2 + \frac 1 4 + \frac 0 8$
$\frac 1 8 = \frac 0 2 + \frac 0 4 + \frac 1 8$
$\frac 5 8 = \frac 1 2 + \frac 0 4 + \frac 1 8$
$\frac 3 8 = \frac 0 2 + \frac 1 4 + \frac 1 8$
$\frac 7 8 = \frac 1 2 + \frac 1 4 + \frac 1 8$

And what if now we just look at the pattern of numerators:

000 100 010 110 001 101 011 111

It's just binary writ backward!

So to compute the Nth color, we want to "mirror image" the bits of N around the decimal point. Another way of doing that is to reverse the bits of N, then shift them right, all the way past the decimal point. Of course bits shifted past the decimal point are normally discarded, but here we can use the opposite of the usual trick and replace a right shift with a divide. Do it in floating point and our bits will get preserved.

Thus, the algorithm to compute the hue of the Nth color in this sequence is:

• Reverse the bits of N
• Convert to floating point
• Divide by 232, assuming N is 32 bit; or use scalbn() if you're fancy

So there is, in fact, a practical use case for reversing the bits of an integer.

You can try it. Click in the area below to add colored circles, and you'll see the quick 'n dirty sequence of colors, starting at 216 degrees. You'll need a CSS3-savvy browser that supports HSL colors. (The JavaScript source is right underneath me!)

If your browser width is such that the number of circles per row is a power of two, you'll see how the distance between colors is strictly one-dimensional.