## CS13002 Programming and Data Structures | ## Section: 5/E, Spring 2006 |

## Assignment 3

Think of the following situation. There is an empty room, and

spersons 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 thespersons is present in the room once and only once.This problem can be solved by using

Gray codes. Ans-bit Gray code is a sequence C_{0},C_{1},..., C_{2s-1}, where each C_{i}is a sequence of exactlysbits, and where each C_{i}differs from the previous code C_{i-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 1000In 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 personiis inside the room at that time, set Bit_{i}=1, else set Bit_{i}=0. The configuration of the room at that time is represented compactly by thes-bit code Bit_{s-1}Bit_{s-2}...Bit_{1}Bit_{0}.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 1Now suppose that C

_{0}, C_{1},..., C_{2s-1}is the Gray code of lengths. Then the Gray code of lengths+1 is constructed as: 0C_{0}, 0C_{1},..., 0C_{2s-1}, 1C_{2s-1},..., 1C_{1}, 1C_{0}. 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 C_{0},C_{1},...C_{2s-1}. Each C_{i}differs from the previous code C_{i-1}in exactly one bit position. Denote this position by pos(i). It turns out that pos(i) is the non-negative integerkfor which 2^{k}dividesibut 2^{k+1}does not. The following table illustrates this construction.

ik= pos(i)C _{i}Action Persons inside room Persons outside room 0 0000 _ 3,2,1,0 1 0 000 1Person 0 enters room 0 3,2,1 2 1 00 11Person 1 enters room 1,0 3,2 3 0 001 0Person 0 leaves room 1 3,2,0 4 2 0 110Person 2 enters room 2,1 3,0 5 0 011 1Person 0 enters room 2,1,0 3 6 1 01 01Person 1 leaves room 2,0 3,1 7 0 010 0Person 0 leaves room 2 3,1,0 8 3 1100Person 3 enters room 3,2 1,0 9 0 110 1Person 0 enters room 3,2,0 1 10 1 11 11Person 1 enters room 3,2,1,0 _ 11 0 111 0Person 0 leaves room 3,2,1 0 12 2 1 010Person 2 leaves room 3,1 2,0 13 0 101 1Person 0 enters room 3,1,0 2 14 1 10 01Person 1 leaves room 3,0 2,1 15 0 100 0Person 0 leaves room 3 2,1,0 Write a program that reads the number

sof 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 integerksuch that 2^{k}dividesibut 2^{k+1}does not. The integerkis called themultiplicityof 2 ini.- 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
sbits.- Write the
main()function that calls the above functions to solve your problem.Report the output of your program for

s= 8 persons.

Sample outputHow 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 ofcodeis one, it suffices to compute the bit-wise AND ofcodewith 2^{k}.- The
k-th bit ofcodecan be flipped by bit-wise XOR ofcodewith 2^{k}.- 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 };