中国环难题和格雷码（二）

继续笔记，上次提到的格雷码的一个迭代规则，在实际编程中，这个算法在计算后置0的时候带有一个循环，因此效率并非最好。TAOCP上提到计算后置0的算法是可以不循环的，这个在TAOCP的前册有提到，不过我没有。但是有一本书，《Hacker's Delight》，上面应该有。不过这些算法可能依赖机器字长，书上提到一个通用的算法，速度很快。
算法的本质和上次提到的一样，快得原因是是找到k的进位不需要循环，而是维护一个长度一致的数组f,其中f[i]表示:

1 如果找到一个块 a[j + 1] = 0, a[j] = a[j - 1] ... = a[i] = 1, a[i - 1] = 0. 那么a[i] = j + 1
2 否则 f[i] = i;

显然，对于一个原始码的一次进位，那个进位的位置就是f[0]指向的位置。(f[-1] = 0)
算法每次都拿f[0]的位置，确定需要修改的g(k)中的变化的位，上次说过了，这个进位的位置和格雷码的变化位是对应的。另j = f[0]，进位发生后, 需要修改一些f，保持f的含义:

         j
         |
         v
..011..11011...11
         |
..011..11100...00

首先f[0] = 0，然后上面可以看出刚刚取出的变化的j,则

f[j] = f[j + 1]       /*这是为了把f[j + 1]指向的块向右扩展一个，因为当前的块变成了 f[j + 1] ~ j */ 
f[j + 1] = j + 1      /*把以前的f[j + 1]清为指向j,规则2*/

书上说这个算法是“眼花缭乱”的快。而且这种算法是很有启发性的，他的意义不仅仅在于这个问题上面，通用性可能应用到其他类似的地方。