## Assignment 3

Think of the following situation. There is an empty room, and s persons are standing outside the room. Then you repeat a sequence of steps. At each step either one person enters the room or one person leaves the room (but not both). Your task is to find a sequence of steps such that every possible combination of the s persons is present in the room once and only once.

This problem can be solved by using Gray codes. An s-bit Gray code is a sequence C0,C1,..., C2s-1, where each Ci is a sequence of exactly s bits, and where each Ci differs from the previous code Ci-1 in exactly one bit position. Here is an example of a 4-bit Gray code:

```   0000
0001
0011
0010
0110
0111
0101
0100
1100
1101
1111
1110
1010
1011
1001
1000
```

In order to translate our problem to Gray codes, let us number the persons by integers between 0 and s-1. Consider a particular point of time. If person i is inside the room at that time, set Biti=1, else set Biti=0. The configuration of the room at that time is represented compactly by the s-bit code Bits-1Bits-2...Bit1Bit0.

Suppose s = 4. Initially all persons are outside the room, so the configuration of the room is 0000. Then Person 0 enters the room, and the configuration changes to 0001. In the next step, Person 1 enters the room changing the configuration to 0011. Then Person 0 leaves the room and the configuration becomes 0010. This corresponds to the first four lines of the above Gray code.

Gray codes can be constructed for any length. Let me first supply an inductive procedure for the construction. The Gray code of length 1 is the following sequence:

```   0
1
```

Now suppose that C0, C1, ..., C2s-1 is the Gray code of length s. Then the Gray code of length s+1 is constructed as: 0C0, 0C1, ..., 0C2s-1, 1C2s-1, ..., 1C1, 1C0. Clearly, the constructed sequence satisfies the desired properties.

In this exercise, we ask you to generate Gray codes iteratively. Suppose you want to construct the s-bit code C0,C1,...C2s-1. Each Ci differs from the previous code Ci-1 in exactly one bit position. Denote this position by pos(i). It turns out that pos(i) is the non-negative integer k for which 2k divides i but 2k+1 does not. The following table illustrates this construction.

ik = pos(i)CiActionPersons inside roomPersons outside room
0 0000 _3,2,1,0
100001Person 0 enters room03,2,1
210011Person 1 enters room1,03,2
300010Person 0 leaves room13,2,0
420110Person 2 enters room2,13,0
500111Person 0 enters room2,1,03
610101Person 1 leaves room2,03,1
700100Person 0 leaves room23,1,0
831100Person 3 enters room3,21,0
901101Person 0 enters room3,2,01
1011111Person 1 enters room3,2,1,0_
1101110Person 0 leaves room3,2,10
1221010Person 2 leaves room3,12,0
1301011Person 0 enters room3,1,02
1411001Person 1 leaves room3,02,1
1501000Person 0 leaves room32,1,0

Write a program that reads the number s of persons and prints the sequence of steps (persons entering and leaving the room) so as to achieve your goal of having each combination in the room once and only once. Proceed as follows:

• Write a function that, given a positive integer i, returns the non-negative integer k such that 2k divides i but 2k+1 does not. The integer k is called the multiplicity of 2 in i.

• Write a function that given a code and a bit position, flips the bit of the code at the given position.

• Write a function that prints a configuration of the room as a sequence of s bits.

• Write the main() function that calls the above functions to solve your problem.

Report the output of your program for s = 8 persons.

Sample output

```   How many persons? 4
i =   0,                              code = 0000, Persons inside :
i =   1, k = 0, Person 0 enters room, code = 0001, Persons inside : 0
i =   2, k = 1, Person 1 enters room, code = 0011, Persons inside : 10
i =   3, k = 0, Person 0 leaves room, code = 0010, Persons inside : 1
i =   4, k = 2, Person 2 enters room, code = 0110, Persons inside : 21
i =   5, k = 0, Person 0 enters room, code = 0111, Persons inside : 210
i =   6, k = 1, Person 1 leaves room, code = 0101, Persons inside : 20
i =   7, k = 0, Person 0 leaves room, code = 0100, Persons inside : 2
i =   8, k = 3, Person 3 enters room, code = 1100, Persons inside : 32
i =   9, k = 0, Person 0 enters room, code = 1101, Persons inside : 320
i =  10, k = 1, Person 1 enters room, code = 1111, Persons inside : 3210
i =  11, k = 0, Person 0 leaves room, code = 1110, Persons inside : 321
i =  12, k = 2, Person 2 leaves room, code = 1010, Persons inside : 31
i =  13, k = 0, Person 0 enters room, code = 1011, Persons inside : 310
i =  14, k = 1, Person 1 leaves room, code = 1001, Persons inside : 30
i =  15, k = 0, Person 0 leaves room, code = 1000, Persons inside : 3
```

Notes

• Represent each code by an unsigned integer.

• In order to check whether the k-th bit of code is one, it suffices to compute the bit-wise AND of code with 2k.

• The k-th bit of code can be flipped by bit-wise XOR of code with 2k.

• You may use the following array for storing powers of 2.
```   const unsigned long bitPos[32] = {
0x00000001, 0x00000002, 0x00000004, 0x00000008,
0x00000010, 0x00000020, 0x00000040, 0x00000080,
0x00000100, 0x00000200, 0x00000400, 0x00000800,
0x00001000, 0x00002000, 0x00004000, 0x00008000,
0x00010000, 0x00020000, 0x00040000, 0x00080000,
0x00100000, 0x00200000, 0x00400000, 0x00800000,
0x01000000, 0x02000000, 0x04000000, 0x08000000,
0x10000000, 0x20000000, 0x40000000, 0x80000000
};
```