Given the coordinates of a point on the Hilbert curve, the distance from the origin to the point can be calculated by means of a state transition table similar to Table 14-2. Table 14-5 is such a table.

Its interpretation is similar to that of the previous section. First, x and y should be padded with leading zeros so that they are of length n bits, where n is the order of the Hilbert curve. Second, the bits of x and y are scanned from left to right, and s is built up from left to right.

A C program implementing these steps is shown in Figure 14-9.

unsigned hil_s_from_xy(unsigned x, unsigned y, int n) {

牋 int i;

牋爑nsigned state, s, row;

牋 state = 0;牋牋牋牋牋牋牋牋牋牋牋牋牋?// Initialize.

牋爏 = 0;

牋 for (i = n - 1; i >= 0; i--) {

牋牋?row = 4*state | 2*((x >> i) & 1) | (y >> i) & 1;

牋牋牋s = (s << 2) | (0x361E9CB4 >> 2*row) & 3;

牋牋牋state = (0x8FE65831 >> 2*row) & 3;

牋爙

牋爎eturn s;

}

[L&S] give an algorithm for computing s from (x, y) that is similar to their algorithm for going in the other direction (Table 14-3). It is a left-to-right algorithm, shown in Table 14-6 and Figure 14-10.

unsigned hil_s_from_xy(unsigned x, unsigned y, int n) {

牋 int i, xi, yi;

牋爑nsigned s, temp;

牋 s = 0;牋牋牋牋牋牋牋牋牋牋牋牋 // Initialize.

牋爁or (i = n - 1; i >= 0; i--) {

牋牋?xi = (x >> i) & 1;牋牋牋牋?// Get bit i of x.

牋牋牋yi = (y >> i) & 1;牋牋牋牋?// Get bit i of y.

牋牋?if (yi == 0) {

牋牋牋牋 temp = x;牋牋牋牋牋牋牋?// Swap x and y and,

牋牋牋牋爔 = y^(-xi);牋牋牋牋牋牋 // if xi = 1,

牋牋牋牋爕 = temp^(-xi);牋牋牋牋?// complement them.

牋牋牋}

`牋牋牋s = 4*s + 2*xi + (xi^yi);牋 // Append two bits to s. `

`牋?/span>} `

牋爎eturn s;

}

## Table 14-6. Lam and Shapiro method for computing S from (X, Y) |
||

If the next (to right) two bits of (x, |
then |
and append to |

(0, 0) |
Swap x and y |
00 |

(0, 1) |
No change |
01 |

(1, 0) |
Swap and complement x and y |
11 |

(1, 1) |
No change |
10 |