Non-recursive Grey code algorithm understanding

Question

This is task from algorithms book.

The thing is that I completely don't know where to start!

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. 

So I know the Gray code for 1 bit should be 0 1, for 2 00 01 11 10 etc.

Many questions

1) Do I know that for n = 1 I can start of with 0 1?

2) How should I understand "start with the n-bit string of all 0's"?

3) "Previous bit string"? Which string is the "previous"? Previous means from lower n-bit? (for instance for n=2, previous is the one from n=1)?

4) How do I even convert 1-bit strings to 2-bit strings if the only operation there is to flip?

This confuses me a lot. The only "human" method I understand so far is: take sets from lower n-bit, duplicate them, invert the 2nd set, add 0's to every element in 1st set, add 1's do every elements in 2nd set. Done (example: 0 1 -> 0 1 | 0 1 -> 0 1 | 1 0 -> 00 01 | 11 10 -> 11 01 11 10 done.

Thanks for any help

Answer 1

The answer to all four your questions is that this algorithm does not start with lower values of n. All strings it generates have the same length, and the i-th (for i = 1, ..., 2ⁿ-1) string is generated from the (i-1)-th one.

Here is the fist few steps for n = 4:

Start with G₀ = 0000

To generate G₁, flip 0-th bit in G₀, as 0 is the position of the least significant 1 in the binary representation of 1 = 0001_b. G₁ = 0001.

To generate G₂, flip 1-st bit in G₁, as 1 is the position of the least significant 1 in the binary representation of 2 = 0010_b. G₂ = 0011.

To generate G₃, flip 0-th bit in G₂, as 0 is the position of the least significant 1 in the binary representation of 3 = 0011_b. G₃ = 0010.

To generate G₄, flip 2-nd bit in G₃, as 2 is the position of the least significant 1 in the binary representation of 4 = 0100_b. G₄ = 0110.

To generate G₅, flip 0-th bit in G₄, as 0 is the position of the least significant 1 in the binary representation of 5 = 0101_b. G₅ = 0111.