关于汉诺塔的非递归 solution 的问题

[hptcyhj]

def iterativeHanoi(n):
    def f(k): return (k%3) if (n%2==0) else (-k%3)
    return [(f(move & (move-1)),
             f((move|(move-1))+1)) for move in range(1,1 << n)]

输出结果（举例）：[(0, 1), (0, 2), (1, 2), (0, 1), (2, 0), (2, 1), (0, 1)]

(0, 1) 表示把第 1 根柱子最上面的盘放到第 2 根上。

我的问题是：

• 为什么可以用位运算符&, | 来输出汉诺塔问题的 solution ，这应该不是一种巧合吧？
• 如果不是巧合，作者是靠什么样的思路想到的？

[SuperFashi]

这叫状态压缩，将一种状态用某种进制表示是在数论或动规题的常用做法。
而汉诺塔这类数论题（包括博弈论中的 sg ）为什么可以用二进制表示出来并用数学方法（例如且或异或等）进行运算，都是可以用数学证明的（大多是数学归纳法），至于证明方法请另行 wiki 。

[Reficul]

汉诺塔问题可以用具体数学里说到的，用归纳法直接求出结果公式。