河内塔的递归解决方案可以使您将N个磁盘从钉A移到C，首先将N-1从A移到B，然后将底部的N-1移到C，然后再将N-移到C从B到C 1个磁盘。本质上，

hanoi(from, to, spare, N):
  hanoi(from, spare, to, N-1)
  moveDisk(from, to)
  hanoi(spare, to, from, N-1)

显然，hanoi（，，，1）采取了一个动作，而hanoi（，，，k）采取了与2 * hanoi（，，_，k-1）+1一样多的动作。解决方案长度按顺序1、3、7、15，…增长。这与（1 << k）-1相同，说明了发布的算法中循环的长度。

如果您自己看一下解决方案，则对于N = 1，您将获得

FROM   TO
          ; hanoi(0, 2, 1, 1)
   0    2    movedisk

对于N = 2，您得到

FROM   TO
          ; hanoi(0, 2, 1, 2)
          ;  hanoi(0, 1, 2, 1)
   0    1 ;   movedisk
   0    2 ;  movedisk
          ;  hanoi(1, 2, 0, 1)
   1    2 ;   movedisk

对于N = 3，您得到

FROM   TO
          ; hanoi(0, 2, 1, 3)
          ;  hanoi(0, 1, 2, 2)
          ;   hanoi(0, 2, 1, 1)
   0    2 ;    movedisk
   0    1 ;   movedisk
          ;   hanoi(2, 1, 0, 1)
   2    1 ;    movedisk
   0    2 ;  movedisk ***
          ;  hanoi(1, 2, 0, 2)
          ;   hanoi(1, 0, 2, 1)
   1    0 ;    movedisk
   1    2 ;   movedisk
          ;   hanoi(0, 2, 1, 1)
   0    2 ;    movedisk

由于该解决方案具有递归性质，因此FROM和TO列遵循递归逻辑：如果您在列上使用中间条目，则上方和下方的部分是彼此的副本，但数字互不相同。这是算法本身的明显结果，该算法不对桩号执行任何算术运算，而仅对它们进行置换。在N= 4的情况下，中间行位于x = 4（上面标有三颗星）。

现在，表达式（X＆（X-1））取消设置了X的最小置位，因此它映射了例如1到7的数字，如下所示：

   1 ->  0
   2 ->  0
   3 ->  2
   4 -> 0 (***)
   5 ->  4 % 3 = 1
   6 ->  4 % 3 = 1
   7 ->  6 % 3 = 0

诀窍在于，由于中间行始终精确地为2的幂，因此恰好设置了一位，所以当您将中间行值（本例中为4）添加到中间行之后，中间行之后的部分等于之前的那一部分。行（即4
= 0 + 4、6 = 2 + 6）。这实现了“ copy”属性，中间行的添加实现了置换部分。表达式（X
|（X-1））+1设置了最低的零位，该位右边有一个零，并将这些零清除，因此它具有与预期相似的属性：

   1 ->  2
   2 ->  4 % 3 = 1
   3 ->  4 % 3 = 1
   4 -> 8 (***) % 3 = 2
   5 ->  6 % 3 = 0
   6 ->  8 % 3 = 2
   7 ->  8 % 3 = 2

至于为什么这些序列实际上产生正确的桩号，让我们考虑一下FROM列。递归解决方案以hanoi（0，2，1，N）开头，因此在中间行（2
（N-1））中，您必须具有movedisk（0，2）。现在，根据递归规则，在（2 （N-2））处需要具有movedisk（0，1）和（2
（N-1））+ 2 （N-2）个movedisk（ 1、2）。这将为from钉创建“
0,0,1”模式，该模式在上表中以不同排列可见（对于0,0,1，请检查第2、4和6行，对于0,0，请检查第1、2、3行）
，2，以及第1,1,0行的第5、6、7行，都是同一模式的所有置换版本）。

现在，在所有具有此特性的函数中，它们以2的幂为单位创建自己的副本，但具有偏移量，因此作者选择了能够对正确的排列模3的那些。这并不是一项艰巨的任务，因为三个整数0..2只有6个可能的排列，并且排列在算法中以逻辑顺序进行。（X
|（X-1））+ 1不一定与河内问题紧密联系，也不必如此；它具有复制属性，并且恰好能够以正确的顺序产生正确的排列就足够了。