这个怎么用？ 河内解答奇怪的塔
当我发现河内塔这个不寻常的迭代解决scheme时，我迷失在互联网上：
for (int x = 1; x < (1 << nDisks); x++) { FromPole = (x & x-1) % 3; ToPole = ((x | x-1) + 1) % 3; moveDisk(FromPole, ToPole); } 这篇文章也有类似的Delphi代码中的一个答案。
然而，对于我的生活，我似乎无法find一个好的解释，为什么这个工程。
任何人都可以帮我理解吗？
河内塔的recursion解决scheme的工作原理是，如果要将N个磁盘从A到C移动，则首先将N-1从A移到B，然后将底部移动到C，然后再移动N-从B到C的1个磁盘。本质上，
hanoi(from, to, spare, N): hanoi(from, spare, to, N-1) moveDisk(from, to) hanoi(spare, to, from, N-1)
很明显，河内（_，_，_，1）采取了一个举措，河内（_，_，_，k）采取与2 *河内（_，_，k-1）+ 1一样多的举动。解的长度按照1,3,7,15的顺序增长……这与（1 << k）-1的顺序相同，它解释了你发布algorithm中循环的长度。
如果你自己看解决scheme，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
由于解决scheme的recursion性质，FROM和TO列遵循recursion逻辑：如果在列上采用中间条目，则上面和下面的部分是彼此的副本，但排列的是数字。 这是algorithm本身的一个显而易见的结果，它不会对挂钩数字进行任何算术运算，而只是对它们进行置换。 在N = 4的情况下，中间行在x = 4处（以三星标记）。
现在expression式（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）。 这实现了“复制”属性，中间行的添加实现了置换部分。 expression式（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列。 recursion解决scheme以河内（0,2,1，N）开始，所以在中间行（2 **（N-1）），你必须有移动（0,2）。 现在通过recursion规则，在（2 **（N-2））你需要有移动（0,1）和在（2 **（N-1））+ 2 **（N-2）移动1,2）。 这为上面的表中不同排列的pegs创build了“0,0,1”模式（针对0,0,1检查行2,4和6，针对0,0检查行1,2,3） ，2，第5,6,7行用于1,1,0，相同模式的所有置换版本）。
现在，所有具有这种属性的function，他们创造了他们自己的权力两个权力，但抵消，作者已经select了那些产生模3正确的排列。 这不是一个公开的艰巨的任务，因为三个整数0..2只有6个可能的排列，并且排列在algorithm中以逻辑顺序进行。 （X |（X-1））+ 1并不一定与河内问题有深层次的联系，也不一定非要; 它具有复制属性就足够了，并且恰好按照正确的顺序产生正确的排列。
antti.huima的解决scheme基本上是正确的，但我想要更严格的东西，这太大了，不适合发表评论。 开始：
首先注意：在这个algorithm的中间步x = 2 N-1 ，“from”peg是0，“to”peg是2 N ％3.这留下了2 （N-1）备用“挂钩。 对于algorithm的最后一步也是如此，所以我们看到实际上作者的algorithm是一个轻微的“作弊”：他们将磁盘从钉0移到钉2 N ％3，而不是固定的指定“到”挂钩“。 这可以改变，没有太多的工作。
最初的河内algorithm是：
hanoi(from, to, spare, N): hanoi(from, spare, to, N-1) move(from, to) hanoi(spare, to, from, N-1)
插入“from”= 0，“to”= 2 N ％3，“spare”= 2 N-1 ％3，我们得到（抑制％3的）：
hanoi(0, 2**N, 2**(N-1), N): (a) hanoi(0, 2**(N-1), 2**N, N-1) (b) move(0, 2**N) (c) hanoi(2**(N-1), 2**N, 0, N-1)
这里的基本观察是：在（c）行中，挂钩正好是移动了2N-1 ％3的河内（0,2N – 1,2N，N-1） 的挂钩 ，即它们恰好是挂钩（a）的这一数额加在他们身上 。
我声称，当我们运行线（c）时，“从”和“到”钉是线（a）的相应钉钉移位2N-1 ％3.这是从简单的，更一般的引理那么在hanoi(a+x, b+x, c+x, N) ，从“和”到“挂钩在hanoi(a, b, c, N)恰好是x。
现在考虑function
f(x) = (x & (x-1)) % 3
g(x) = (x | (x-1)) + 1 % 3
为了certificate给定的algorithm有效，我们只需要certificate：
- f（2 N-1 ）== 0和g（2 N-1 ）== 2 N
- 对于0 <i < 2N ，我们有f（ 2N -i）== f（ 2N + i）+ 2N ％3，并且g（ 2N -i）== g（ 2N + i）+ 2 N ％3。
这两个都很容易显示。
这不是直接回答这个问题，但是发表评论太长了。
我总是通过分析下一步应该移动的磁盘的大小来做到这一点。 如果你看看被移动的磁盘，它会出现：
1 disk : 1 2 disks : 1 2 1 3 disks : 1 2 1 3 1 2 1 4 disks : 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1
奇怪的大小总是向相反的方向移动，以便如果钉（0,1,2，重复）或（2,1,0，重复）。
如果你看一下这个模式，那么移动的环就是移动次数和移动次数+ 1的最高位。
