Introduction
Operating Systems have a need for extremely compact data structures, as often these need to be stored wholly in memory. Examples of this are free memory lists, page tables and disk space bitmaps. This practical Case Study will refresh your knowledge of bit operations, necessary to manipulate such compact data structures. We will use a simple variant of the card game poker as the inspiration for our compact data structure.In this exercise, you will model a deck of playing cards as a bit 1eld. Only six bits are
required to fully describe a card, two for the suit and four for the value. An extra bit as been added to the structure to encode the colour of the card.
A second bit 1eld will be used to store the number of pairs contained in a hand. Read this section fully before attempting any of the exercises. These instructions contain some background information, the task to perform, sample code and some system documentation extract.
2 Structure of the bit 1elds
2.1 The card bit 1eld
As explained above only six bits are really needed to describe a playing card. However a seventh bit has been added, this is only as a matter of convenience, as you will see below it makes the card 00000000 an invalid card and thus the standard C logic tests can be used to test if a card is valid or not. As only seven bits are required you can use one byte to store the value. A C-type de1nition of:typedef unsigned char card;
would be useful to describe this new data type, as we don’t treat it as a whole but as a bit set. The byte will have the following format, bits 0 & 1 encode the suit, bits 2, 3, 4, & 5 encode the value and bit 6 encodes the colour. Bit 7 is unused. Each of these subsections has the values as depicted in Tables 1, 2 & 3.
Following this table, the Ace of Hearts would be 1000000 (64) and the King of Spades would be 011001122(51). You should draw a picture of what this bit 1eld looks like, noting which of the 8 bits are assigned to which values.
2.2 The pairs bit 1eld
The second bit 1eld is used to hold the number of pairs in a hand. It has the format that the four least signi1cant bits (bits 0-3) contain the number of pairs contained in a hand and the four most signi1cant bits (bits 4-7) hold the value of the card as detailed in Table 2. A C typedef of:typedef unsigned char pairs;
will be useful here. You should draw a picture of what this bit 1eld looks like, noting which of the 8 bits are assigned to which values.
3 Bit Operations
The C programming language provides a full set of bit manipulation operators:& bitwise and
| bitwise or
ˆ bitwise exclusive or
˜ ones compliment
>> right shift
<< left shift
These operators can be used to manipulate values at the bit level. There are four men upsetting a bit, testing if a bit is set and toggling a bit. To set a bit we use the bitwise or operator. To do this we bitwise or our value with a mask with the bits, we want to turn on set to 1 and all others 0. For example, to turn on the third bit our mask would be 00000100
operations that we perform, setting a bit, upsetting a bit, testing if a bit is set and toggling a bit. To set a bit we use the bitwise or operator. To do this we bitwise or our value with a mask with the bits we want to turn on set to 1 and all others 0. For example, to turn on the third bit our mask would be 00000100
(the subscript means that the number is expressed in binary, no subscript means decimal).
To unset a bit we use the bitwise and operator. To do this we bitwise and our value with a mask with the bits we want to unset set to 0 and all others 1. For example to unset the sixth bit our mask would be 11011111. We can also use the ones complement operator to invert a mask used to set a bit. To test if a bit is set we use the bitwise and operator. To do this we bitwise and our value with a mask with the bits we want to test set to 1 and all others 0. For example to test if the 1fth bit is set our mask would be 00010000.
To toggle a bit we use the bitwise exclusive or operator. To do this we bitwise exclusive or 2 our value with a mask with the bits we want to toggle set to 1 and all others 0. For example, to toggle the fourth bit our mask would be 00001000
We can use the left shift operator to construct masks, by shifting the value 1 the required 2 number of positions. The shift operators can also be used, with masking to extract sub1elds or to encode sub-1elds.
4 Number Systems
In the previous section, various masks were presented, however, the C programming language doesn’t allow numbers to be expressed in binary. C allows three styles of number: decimal, octal and hexadecimal. Decimal numbers are the numbers we use every day. Octal numbers are a base 8 system. To specify to the C compiler that a number is octal you add the pre1x 0. For example, the decimal number 23 would be written in octal in a C program as 027. The advantage of octal numbers is that each digit represents exactly three bits. Octal numbers are often used for specifying permissions in Unix.Hexadecimal numbers are a base 16 system, the letters a-f or A-F is used for the extra positions. To specify to the C compiler that a number is a hexadecimal you add the pre1x 0x. For example, the decimal number 23 would be written in hexadecimal in a C program as 0x17. The advantage of hexadecimal numbers is that each digit represents exactly four bits. Hexadecimal numbers are often used for specifying masks and memory addresses. Table 4 shows equivalent values for the numbers 1-16.
5 Programming Tasks
You should begin by reading the example code carefully. It contains some hints and comments on where to 1ll in the blanks. The 1rst step will be writing a function that displays the card. You can use the various bit 1elds as an index to an array of strings once extracted. The arrays are:static char*
static char*
static char*
suits[] = {"Hearts","Diamonds",
"Clubs","Spades"};
values[]= {"Ace","Two","Three","Four",
"Five","Six","Seven","Eight",
"Nine","Ten","Jack","Queen",
"King"};
colour[]= {"Black","Red"};
You should print the card as “Ace of Hearts, is Red”, with one card per line. Test your function by creating cards individually and displaying them. Once you can display cards you should then write a function that populates a deck (array of 52) with cards. The deck should be sorted in order by suit, that is Ace to King of hearts, then diamonds etc. With some clever arithmetic, you can accomplish this in one pass of the deck. Print the deck once you have populated it. Once you have a deck, develop a method for shu[ing it. As a hint investigate the C standard library functions rand() and rand(). Shu[ing involves mixing the cards up so that the order is random. Print the deck a second time and check that you have actually mixed up the deck. so that the order is random. Print the deck a second time and check that you have actually mixed up the deck.
Now that we have a working shu[ing algorithm we are ready to play cards. To keep things reasonably simple we are going to simulate a simpli1ed version of poker. In this game, 5 hands of 1ve cards are dealt. There is no swapping of cards and the winner is determined by who has the highest pair. A pair of cards are cards that have the same value e.g. the Ace of Hearts and the Ace of Spades are a pair. The number of pairs contained in a hand, three or four of kinds have no bearing on the result. If none of the 1ve hands contains a pair, or two hands contain the same highest pair, the game is considered drawn.
Although traditional poker has the Ace card being a turning point, that is it can be the low card or the high card, the cards in this game have a 1xed order, as described in Table 2. This means that Aces are low and can be beaten by any other pair. You should develop a program that implements this game. Additionally, you should print each of the hands sorted in order of value, print the number of pairs in each hand and if there is at least 1 pair print the value of the highest pair. Once all 1ve hands have been printed you should indicate if there were a winner and the value of the pair that won. If there was no winner you should indicate that the game was drawn. See Figures 1 & 2 for some
Description
The rand() function returns a pseudo-random integer between 0 andRAND MAX. The srand() function sets its argument as the seed for a new sequence of pseudo-random integers to be returned by rand(). These sequences are repeatable by calling srand() with the same seed value. If no seed value is provided, the rand() function is automatically seeded with a value of 1. The function rand() is not reentrant or thread-safe, since it uses hidden state that is mod-i1ed on each call. This might just be the seed value to be used by the next call, or it might be something more elaborate. In order to get reproducible behaviour in a threaded application, this state must be made explicit. The function rand r() is supplied with a pointer to an unsigned int, to be used as a state. This is a very small amount of state, so this function will be a weak pseudo-random generator. Try drand48 r(3) instead.
Return Value
The rand() and rand r() functions return a value between 0 and RAND MAX. The srand() function returns no value.Product Images
Thank you!
ReplyDelete