汉诺塔问题是递归的经典案例了。今天看到matrix67写的位运算简介及实用技巧， 其中提到了用位运算解决汉诺塔问题的思路，所以尝试用位运算来实现汉诺塔的非递归算法。
核心思路是：
Gray码改变的是第几个数，Hanoi塔就该移动哪个盘子。
而我们知道二进制数和格雷码有对应关系，第 $n$ 位格雷码等于 n ^ (n >> 1)，则第 $n$ 位格雷码到第 $n+1$ 位格雷码变化的位数可以通过二者相异或求得：(n ^ (n >> 1)) ^ ((n + 1) ^ ((n + 1) >> 1))，而这等于((n ^ (n + 1)) + 1) >> 1，由此可知，在 $\log_2$ 的意义下等价于 n ^ (n + 1)。最后再对 n ^ (n + 1) 进行位计数(counting bits)就得到了我们想要的值。
由于一共只有32个值，所以这里利用de Bruijn序列构造了一个散列函数，其效果类似于$ hash(x) = \log_2(x+1)-1,\ x=2^{j+1}-1$
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MOD(x) ((x) + 'A' - 1)
#define DISP(x, y) printf("%c -> %c\n", MOD(x), MOD(y))
int hash(uint32_t);
int main() {
int n, i, j, even = 0;
printf("How many disks?\n");
scanf("%d", &n);
uint8_t *pos = malloc(n), circle[3];
memset(pos, 1, n);
circle[0] = 2 + n % 2;
circle[1] = 3 - n % 2;
circle[2] = 1;
uint32_t m = 0;
for (i = 0, j = 0; j < n; m++, j = hash(m ^ m + 1))
if (even = 1 - even) {
DISP(pos[j], circle[i]);
pos[j] = circle[i];
i = (i + 1) % 3;
} else {
DISP(pos[j], 6 - pos[j] - pos[0]);
pos[j] = 6 - pos[j] - pos[0];
}
return 0;
}
int hash(uint32_t x) {
int m[32] = {31, 0, 27, 1, 28, 13, 23, 2, 29, 21, 19, 14, 24, 16, 3, 7,
30, 26, 12, 22, 20, 18, 15, 6, 25, 11, 17, 5, 10, 4, 9, 8};
return m[((x + 1) * 0x077CB531U) >> 27];
}