Sundry Miscellanea

Suppose you want a variable to cycle between three different values in a loop, like this.

If this code is executed in a loop, then x will alternate between the values a, b, and c repeatedly. But how may we achieve the same effect without any branching? Tricky...here's a little scheme I've cooked up to do just that. It cheats by using two variables x and y. The mysterious "plus-in-a-circle" operation is bitwise exclusive-or (exor).

First, before the loop starts, initialize x and y, and precompute the magic constant s as follows.

Then inside the loop execute the following non-branching code.

Note that x cycles between the following three values, because of the self-inverse property of exor (see Alternating without a branch).

So if we exor x with the magic constant s we get a value that cycles between a, b, and c, because of the self-inverse property of exor, once again.

There's a secret connection between this scheme and the Fibonacci numbers...