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 workshop will refresh your knowl- edge of bit operations, necessary to manipulate such compact data-structures.
Consider a theater that has 320 seats. When booking a ticket the agent needs to find a free seat and allocate it to you. If we were to write a booking program we would need to search a data-structure looking for a free seat, assuming that seats are allocated on a first come first served basis, and that we are only interested in if a seat is free or not.
There are several ways of creating this data-structure, as an array with one element per seat, as a linked list with one element per seat and as a bitmap with one bit per seat. In the array case we would need one int per seat (as a boolean value for free/not free), for a total of 320 ints. Assuming that ints and pointers are 4 bytes in size, this is 4 × 320 or 1280 bytes.
If we use a linked list, we would need 1 int for the seat number and a pointer to the next element. The total size of each element is thus 8 bytes. A linked list has the advantage that existence of a node indicates that a seat is free, so when the theater is sold out the list will be empty, however when all the seats are available we need 320 elements at 8 bytes each for a total of 2560 bytes.
If we use a bitmap, we need 1 bit per seat, for a total of 320 bits. As there are 8 bits per byte, we need a total of 40 bytes.
As another example of this, the former Olympic stadium in Sydney has 83500 seats. An array of free seats will need 334000 bytes of storage, a linked list will require 668000 bytes of storage, and a bitmap will require 10438 bytes of storage.
As you can see the amount of storage needed is significantly smaller for a bitmap than for other methods of representation. However there are some down sides. One is that searching a bitmap is a little more complicated than searching an array or list. A tradeoff needs to be reached, between the size saving and the complexity of the searching. If our booking program was for the theater then and array or list might suffice, but for Telstra Stadium only the bitmap might be suitable. This example is rather simplified, as usually when booking a ticket at a theater or stadium, the booking agent will record the details of the person who booked the seat, and thus one data-structure that records this information as well as allowing for unbooked seats would be more suitable.
Operating Systems often need a fast compact way of finding something free, either memory pages or disk blocks, and thus bitmaps are often suitable. An- other area that bitmaps are used is as flags to system calls, here a whole group of boolean values are lumped together as a bit-field.
In this exercise you will model a deck of playing cards as a bit field. 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 field 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 per- form, sample code and some system documentation extracts.
The C programming language provides a full set of bit manipulation operators:
These operators can be used to manipulate values at the bit level. There are four main operations that we perform, setting a bit, unsetting 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 2 (the subscript 2 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 2 . We can also use the ones compliment 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 fifth bit is set our mask would be 00010000 2
To toggle a bit we use the bitwise exclusive or operator. To do this we bitwise exclusive or 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 2.
We can use the left shift operator to construct masks, by shifting the value 1 the required number of positions.
The shift operators can also be used, with masking to extract subfields or to encode subfields.
Binary Hexadecimal Octal Decimal
0000 0 0 0
0001 1 1 1
0010 2 2 2
0011 3 3 3
0100 4 4 4
0101 5 5 5
0110 6 6 6
0111 7 7 7
1000 8 10 8
1001 9 11 9
1010 A 12 10
1011 B 13 11
1100 C 14 12
1101 D 15 13
1110 E 16 14
1111 F 17 15
Table 1: Values for 1-16
In the previous section various masks were presented, however the C program- ming 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 prefix 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 are used for the extra positions. To specify to the C compiler that a number is hexadecimal you add the prefix 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 1 shows equivalent values for the numbers 1-16.
The card bit field
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 2 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 definition 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, bit 2 encodes the colourbits 3, 4, 5, & 6 encode the value. Bit 7 is unused. Each of these subsections has the values as depicted in Tables 2, 3 & 4.
Following this table the Ace of Hearts would be 0000100 2 (4) and the King of Spades would be 1100011 2 (99).
The pairs bit field
The second bit field is used to hold the number of pairs in a hand. It has the format that the four least significant bits (bits 0-3) contain the number of pairs contained in a hand and the four most significant bits (bits 4-7) hold the value of the card as detailed in Table 3. A C typedef of:
typedef unsigned char pairs ;
will be useful here.
You should begin by reading the example code carefully. It contains some hints and comments on where to fill in the blanks.
The first step will be writing a function that displays the card. You can use the various bit fields as an index to an array of strings once extracted. The arrays are:
static char * suits [ ] = {”Hearts” ,”Diamonds” ,
”Clubs” ,”Spades”};
static char *values []= {”Ace” ,”Two” ,”Three” ,”Four” ,
”Five” ,”Six” ,”Seven” ,”Eight” ,
”Nine” ,”Ten” ,”Jack” ,”Queen” ,
”King”};
static char *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 shuffling it. As a hint investigate the C standard library functions rand() and srand(). Shuffling 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.
Now that we have a working shuffling algorithm we are ready to play cards. To keep things reasonably simple we are going to simulate a simplified version
Bit value Value encoded
00 2 Hearts
01 2 Diamonds
10 2 Clubs
11 2 Spades
Table 2: Values of the Suit bits
Bit value Value encoded
0000 2 Ace
0001 2 Two
0010 2 Three
0011 2 Four
0100 2 Five
0101 2 Six
0110 2 Seven
0111 2 Eight
1000 2 Nine
1001 2 Ten
1010 2 Jack
1011 2 Queen
1100 2 King
Table 3: Values of the Value bits
Bit value Value encoded
0 2 Black
1 2 Red
Hand 1:
Six of Spades, is Black
Seven of Diamonds, is Red
Eight of Spades, is Black
Ten of Hearts, is Red
Queen of Spades, is Black
Number of pairs: 0
Hand 2:
Three of Spades, is Black
Five of Diamonds, is Red
Five of Clubs, is Black
Nine of Diamonds, is Red
Queen of Diamonds, is Red
Number of pairs: 1
Highest pair is: Five
Hand 3:
Three of Clubs, is Black
Seven of Hearts, is Red
Nine of Clubs, is Black
Jack of Clubs, is Black
Jack of Spades, is Black
Number of pairs: 1
Highest pair is: Jack
Hand 4:
Two of Diamonds, is Red
Four of Spades, is Black
Seven of Clubs, is Black
Eight of Diamonds, is Red
King of Hearts, is Red
Number of pairs: 0
Hand 5:
Ace of Hearts, is Red
Six of Clubs, is Black
Seven of Spades, is Black
Nine of Spades, is Black
Nine of Hearts, is Red
Number of pairs: 1
Highest pair is: Nine
Winner is hand 3 with a pair of Jacks
Figure 1: Example output of a game with a winner. (The output has been wrapped to two columns to fit on the page.)
of poker. In this game 5 hands of five 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 a kinds have no bearing on the result. If none of the five 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 fixed order, as described in Table 3. 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 five hands have been printed you should indicate if there was 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 sample output.
Your hands should be stored in an array for ease of use and when sorting the hand you should investigate the C standard library function qsort(), which might make things easier for you.
Hand 1:
Three of Clubs, is Black
Five of Hearts, is Red
Seven of Spades, is Black
Queen of Clubs, is Black
King of Spades, is Black
Number of pairs: 0
Hand 2:
Three of Diamonds, is Red
Five of Diamonds, is Red
Seven of Hearts, is Red
Queen of Diamonds, is Red
King of Hearts, is Red
Number of pairs: 0
Hand 3:
Ace of Hearts, is Red
Two of Clubs, is Black
Seven of Diamonds, is Red
Nine of Spades, is Black
Jack of Clubs, is Black
Number of pairs: 0
Hand 4:
Ace of Clubs, is Black
Five of Clubs, is Black
Nine of Diamonds, is Red
Jack of Diamonds, is Red
King of Clubs, is Black
Number of pairs: 0
Hand 5:
Three of Hearts, is Red
Four of Hearts, is Red
Ten of Hearts, is Red
Queen of Hearts, is Red
King of Diamonds, is Red
Number of pairs: 0
Hand 1:
Three of Clubs, is Black
Five of Hearts, is Red
Seven of Spades, is Black
Queen of Clubs, is Black
King of Spades, is Black
Number of pairs: 0
Hand 2:
Three of Diamonds, is Red
Five of Diamonds, is Red
Seven of Hearts, is Red
Queen of Diamonds, is Red
King of Hearts, is Red
Number of pairs: 0
Hand 3:
Ace of Hearts, is Red
Two of Clubs, is Black
Seven of Diamonds, is Red
Nine of Spades, is Black
Jack of Clubs, is Black
Number of pairs: 0
Hand 4:
Ace of Clubs, is Black
Five of Clubs, is Black
Nine of Diamonds, is Red
Jack of Diamonds, is Red
King of Clubs, is Black
Number of pairs: 0
Hand 5:
Three of Hearts, is Red
Four of Hearts, is Red
Ten of Hearts, is Red
Queen of Hearts, is Red
King of Diamonds, is Red
Number of pairs: 0
Drawn game
Figure 2: Example output of a game without a winner. (The output has been wrapped to two columns to fit on the page.)