非递归格雷码算法理解

Question

这是算法书的任务。

事情是我完全不知道从哪里开始！

Trace the following non-recursive algorithm to generate the binary reflexive 
Gray code of order 4. Start with the n-bit string of all 0’s. 
For i = 1, 2, ... 2^n-1, generate the i-th bit string by flipping bit b in the 
previous bit string, where b is the position of the least significant 1 in the 
binary representation of i. 

所以我知道1位的格雷码应该是0 1，2个00 01 11 10等

许多问题

1）我知道，对于n = 1，我可以启动0 1？

2）我应该怎么理解“从0开始的所有0的n位串”？

3）“Previous bit string”？哪个字符串是“之前”？以前的意思是从较低的n位？ （例如，对于n = 2，以前是来自n = 1的那个）？

4）如果唯一的操作是翻转，我怎么才能将1位字符串转换为2位字符串？

这使我困惑不已。到目前为止，我所理解的唯一的“人类”方法是：从低n位取集，复制它们，颠倒第二组，将第一组中的每个元素加0，将第二组中的每个元素加1。做（例如：0 1 - >0 1 | 0 1 - >0 1 | 1 0 - >00 01 | 11 10 - >11 01 11 10做

感谢所有帮助

Answer 1

答案全部四个您的问题是，这种算法不具有的n较低值开始。 。它产生所有字符串具有相同的长度，并且i-th（对于i = 1，...，2 ^ñ -1）从(i-1)-th一个生成的字符串。

这里是n的拳头几步= 4：

开始以G = 0000

为了生成ģ，翻转0-th位G中，作为0是的至少显著1在1 = 0001的二进制表示的位置 _b。 G = 0001。

要生成ģ，翻转1-st位G中，如1是的至少显著1在2 = 0010 _b二进制表示的位置。 G = 0011。

要生成ģ，翻转0-th位G中，作为0是的至少显著1在3 = 0011 _b二进制表示的位置。G = 0010。

为了产生ģ，翻转2-nd位G中，作为2是的至少显著1在4 = 0100 _b二进制表示的位置。 G = 0110。

为了产生ģ，翻转0-th位G中，作为0是的至少显著1在5 = 0101 _b二进制表示的位置。 G = 0111。