用位运算解决汉诺塔问题

2022-03-27

汉诺塔问题是递归的经典案例了。今天看到matrix67写的位运算简介及实用技巧, 所以尝试用位运算来实现汉诺塔的非递归算法。

核心思路是 Gray码改变的是第几个数,Hanoi塔就该移动哪个盘子。 而我们知道二进制数和格雷码有对应关系,第 $n$ 位格雷码等于 n ^ (n >> 1),则第 $n$ 位格雷码到第 $n+1$ 位格雷码变化的位数可以通过二者相异或求得:(n ^ (n >> 1)) ^ ((n + 1) ^ ((n + 1) >> 1)),而这等价于 n ^ (n + 1)

完整的代码如下

#include <stdio.h>
#define FLIP(x) ((x) + 'A' - 1)
#define DISP(x, y) printf("%c -> %c\n", FLIP(x), FLIP(y))
int qlog2(unsigned int x);
int main() {
  int n;
  scanf("%d", &n);
  int pos[n], circle[3];
  for (int i = 0; i < n; i++) pos[i] = 1;
  circle[2] = 1;
  if (n % 2 == 0) {
    circle[0] = 2;
    circle[1] = 3;
  } else {
    circle[0] = 3;
    circle[1] = 2;
  }
  int i = 0, even = 1, j;
  unsigned int m = 0;
  while ((j = qlog2(m ^ (m + 1))) < n) {
    m++;
    if (even) {
      DISP(pos[j], circle[i]);
      pos[j] = circle[i++];
      i %= 3;
    } else {
      DISP(pos[j], 6 - pos[j] - pos[0]);
      pos[j] = 6 - pos[j] - pos[0];
    }
    even = 1 - even;
  }
  return 0;
}
int qlog2(unsigned int x) {
  int n = 1;
  if ((x >> 16) == 0) {
    n += 16;
    x <<= 16;
  }
  if ((x >> 24) == 0) {
    n += 8;
    x <<= 8;
  }
  if ((x >> 28) == 0) {
    n += 4;
    x <<= 4;
  }
  if ((x >> 30) == 0) {
    n += 2;
    x <<= 2;
  }
  n -= (x >> 31);
  return 31 - n;
}

UVa 201 正方形 题解

7-2 一元多项式的乘法与加法运算 题解