# Loopless Ruler

**Posted:**April 13, 2014

**Filed under:**C Leave a comment

This function (based on Algorithm L for loopless Gray code generation in TAOCP 7.2.1.1):

void ruler(int n) { int f[n+1]; for (int j = 0; j <= n; j++) { f[j] = j; } while(true) { visit(f,n+1); int j = f[0]; f[0] = 0; if (j == n) break; f[j] = f[j+1]; f[j+1] = j+1; } }

enables us to compute the “ruler function”, ρ for 1, 2, 3…:

0 1 0 2 0 1 0 3 0 1 0 2 0 1 0...

It’s a “loopless” algorithm and uses f, an array of “focus pointers” to keep track of what’s going on.

The ruler function ρ(n) is essentially the number of trailing 0’s in the binary representation of n.

This is what’s printed by ruler(4):

0 1 2 3 4 1 1 2 3 4 0 2 2 3 4 2 1 2 3 4 0 1 3 3 4 1 1 3 3 4 0 3 2 3 4 3 1 2 3 4 0 1 2 4 4 1 1 2 4 4 0 2 2 4 4 2 1 2 4 4 0 1 4 3 4 1 1 4 3 4 0 4 2 3 4 4 1 2 3 4

The left hand side is the ruler function of course, what are the other values?

It’s clearer if we print f in reverse and match up with binary representations:

00000 43210 00001 43211 00010 43220 00011 43212 00100 43310 00101 43311 00110 43230 00111 43213 01000 44210 01001 44211 01010 44220 01011 44212 01100 43410 01101 43411 01110 43240 01111 43214

If n[j] is the jth binary digit of n, then f[j] is just j, unless n[j] is the first of a block of 1’s, in which case f[j] is the index of the first 0 after that block.

For example, 01101, has block starting at 0 and ending at 1, so f[0] = 1, and another block starting at 2, ending at 4, so f[2] = 4; for other j, f[j] = j, so the focus pointers are 43411.

If n is of the form:

j k 01110111

with f[0] = k, f[k] = k, f[k+1] = j

0n incrementing we get:

j k 01111000

Now f[0] = 0, f[k] = j and f[k+1] = k+1, other values of f are the same

If k is 0, then we go from:

j k 01110

with f[0] = 0, f[1] = j

to:

j k 01111

with f[0] = 0, f[1] = 1

Either way, we can see that the inner loop of `ruler`

is correct.