Week 02

Stacks, Queues, Priority Queues

Stacks, Queues, PriorityQs 2/82

Computer systems frequently make use of:

stacks ... last-in-first-out lists
- e.g. used to represent function local variables
queues ... first-in-first-out lists
- e.g. used to ensure fair access to a resource
priority queues ... highest-priority-out lists
- e.g. used to represent weighted lists of processes

... Stacks, Queues, PriorityQs 3/82

All of these data structures have

a sequence of items
an operation to insert an item into the sequence
an operation to remove an item from the sequence

Data structures differ in

stack ... insert adds on top, removes from top
queue ... insert adds at tail, removes from head
priorityQ ... inserts item with a given priority, removes item with highest priority

Example Stack/Queue/PriorityQ Usage 4/82

Starting from data containing one item, insert 3

... Example Stack/Queue/PriorityQ Usage 5/82

Then insert 6

... Example Stack/Queue/PriorityQ Usage 6/82

Then insert 2

... Example Stack/Queue/PriorityQ Usage 7/82

Then remove item

... Example Stack/Queue/PriorityQ Usage 8/82

Then insert 4

... Example Stack/Queue/PriorityQ Usage 9/82

Then remove item

... Example Stack/Queue/PriorityQ Usage 10/82

Then remove item

Priority Queue Data Structure 11/82

Priority Queue: Highest-priority-out protocol

insert operation called enter (or enqueue())
remove operation called leave (or dequeue())
has a head (next for removal), a tail (lowest-priority), and a size

Priority Queue interface:

typedef struct priorityq * PriorityQ;
PriorityQ initPriorityQ(void);
int  enterPriorityQ(PriorityQ q, Item val);
Item leavePriorityQ(PriorityQ q);
int  isEmptyPriorityQ(PriorityQ q);
void destroyPriorityQ(PriorityQ q);

Example Priority Queue Client 12/82

A program to use a priority Queue. Assume Item has been defined as

typedef struct item Item;
struct item{
    int priority;
    char * data;
};

#include <stdio.h>
#include "PriorityQueue.h"
int main(void)
{
   char buffer[MAX_INPUT];
   PriorityQ pq = initPriorityQ();
   Item   item;
   int priority;
   while(fgets(buffer,MAX_INPUT,stdin) != NULL){
        if(sscanf(buffer,"%d %[^\n]",&priority,buffer) != 2) break;
        if(enterPriorityQ(pq,newItem(priority,buffer)) == 0) break;
   }    

   while (!isEmptyPriorityQ(pq)) {
      item = leavePriorityQ(pq);
      printf("%s\n", item->data);
      destroyItem(item);
   }
   destroyPriorityQ(pq);
   return 0;
}

Exercise 1: Implement a Priority Queue 13/82

Use a fixed sized un-ordered array. The function, enterPriorityQueue should return 0 if the array is full
Modify your solution to use a dynamically allocated array that can use realloc if the array gets full.

Bit Manipulation

Bits in Bytes in Words 15/82

Values that we normally treat as atomic can be viewed as bits, e.g.

char = 1 byte = 8 bits ('a' is 01100001)
short = 2 bytes = 16 bits (42 is 0000000000101010)
int = 4 bytes = 32 bits (42 is 0000000000...0000101010)
double = 8 bytes = 64 bits

The above are common sizes and don't apply on all hardware
(e.g. sizeof(int) might be 16 or 64 bits, sizeof(double) might be 32 bits)

C provides a set of operators that act bit-by-bit on pairs of bytes.

E.g. (10101010 & 11110000) yields 10100000 (bitwise AND)

C bitwise operators: & | ^ ~ << >>

Binary Constants 16/82

Literal numbers in decimal, hexadecimal, octal, binary.

In hexadecimal, each digit represents 4 bits

   0100 1000 1111 1010 1011 1100 1001 0111
0x   4    8    F    A    B    C    9    7

In octal, each digit represents 3 bits

   01 001 000 111 110 101 011 110 010 010 111
0   1  1   0   7   6   5   3   6   2   2   7

In binary, each digit represents 1 bit

0b01001000111110101011110010010111

Bitwise AND 17/82

The & operator

takes two values (1,2,4,8 bytes), treats as sequence of bits
performs logical AND on each corresponding pair of bits
result contains same number of bits as inputs

Example:

  00100111           AND | 0  1
& 11100011           ----|-----
  --------             0 | 0  0
  00100011             1 | 0  1

Used for e.g. checking whether a bit is set

Exercise 2: Checking for odd numbers 18/82

One obvious way to check for odd numbers in C

int isOdd(int n) { return (n%2) == 1; }

Could we use & to achieve the same thing? How?

Aside: an alternative to the above

#define isOdd(n)  ((n)%2) == 1)

What's the difference between the function and the macro?

Bitwise OR 19/82

The | operator

takes two values (1,2,4,8 bytes), treats as sequence of bits
performs logical OR on each corresponding pair of bits
result contains same number of bits as inputs

Example:

  00100111            OR | 0  1
| 11100011           ----|-----
  --------             0 | 0  1
  11100111             1 | 1  1

Used for e.g. ensuring that a bit is set

Bitwise NEG 20/82

The ~ operator

takes a single value (1,2,4,8 bytes), treats as sequence of bits
performs logical negation of each bit
result contains same number of bits as input

Example:

~ 00100111           NEG | 0  1
  --------           ----|-----
  11011000               | 1  0

Used for e.g. creating useful bit patterns

Exercise 3: Bit-manipulation 21/82

Assuming 8-bit quantities and writing answers as 8-bit bit-strings ...

What are the values of the following:

25, 65, ~0, ~1, 0xFF, ~0xFF
(01010101 & 10101010), (01010101 | 10101010)
(x & ~x), (x | ~x)

How can we achieve each of the following:

ensure that the 3rd bit from the RHS is set to 1
ensure that the 3rd bit from the RHS is set to 0

Bitwise XOR 22/82

The ^ operator

takes two values (1,2,4,8 bytes), treats as sequence of bits
performs logical XOR on each corresponding pair of bits
result contains same number of bits as inputs

Example:

  00100111           XOR | 0  1
^ 11100011           ----|-----
  --------             0 | 0  1
  11000100             1 | 1  0

Used in e.g. generating random numbers, building adder circuits

Left Shift 23/82

The << operator

takes a single value (1,2,4,8 bytes), treats as sequence of bits
and a small positive integer x
moves (shifts) each bit x positions to the left
left-end bit vanishes; right-end bit replaced by zero
result contains same number of bits as input

Example:

  00100111 << 2      00100111 << 8
  --------           --------
  10011100           00000000

** undefined and not recommended for signed quantities.

Right Shift 24/82

The >> operator

takes a single value (1,2,4,8 bytes), treats as sequence of bits
and a small positive integer x
moves (shifts) each bit x positions to the right
right-end bit vanishes; left-end bit replaced by zero**
result contains same number of bits as input

Example:

  00100111 >> 2      00100111 >> 8
  --------           --------
  00001001           00000000

** if signed quantity, sign bit replaces left-end bit

Exercise 4: Bitwise Operations 25/82

Given the following variable declarations:

    // a signed 8-bit value
signed char x = 0b01010101;
    // an 8-bit value
unsigned char y = 0b11001100;

What is the value of each of the following expressions:

(x & y)
(x ^ y)
(x << 1)
(y << 2)
(x >> 1)
(y >> 1)
(x << 3)
(y << 9)
(x >> 8)

Exercise 5: Bit Shifting Exercises 26/82

Write a line of code to multiply an unsigned int by 2 using bit shift operations.
Write a line of code to divide an unsigned int by 4 using bit shift operations.
Write a line of code to set the 3rd least significant bit of an unsigned int to 1.
Write a function to find 2 to the power of n.
Write a function to print out an int in binary.

Memory

The C View of Data 28/82

A C program sees data as a collection of variables

int g = 2;

int main(void)
{
    int   i;
    int   v[5]
    char *s = "Hello";
    int  *n = malloc(sizeof(int));
    ...
}

Each variable has properties e.g. name, type, ...

... The C View of Data 29/82

Variables are examples of computational objects

Each computational object has

a location in memory (obtainable via &)
a value (ultimately just a bit-string)
a name (unless created by malloc())
a type, which determines ...
- its size (in units of whole bytes, sizeof)
- how to interpret its value; what operations apply
a scope (where it's visible within the program)
a lifetime (during which part of program execution it exists)

... The C View of Data 30/82

Memory regions during C program execution ...

... The C View of Data 31/82

Example of runtime stack during call to h()

[Diagram:Pics/memory/stack-frames-small.png]

Exercise 6: Properties of Variables 32/82

Identify the properties of each of the named objects in the following:

int a;           // global int variable

int main(void) {
   int  b;       // local int variable
   static char c;// local static char variable
   char d[10];   // local char array
   ...
}

int e;           // global? int variable

int f(int g) {  // function + parameter
   double h;     // local double variable
   ...
}

The Physical View of Data 33/82

Memory = indexed array of bytes

[Diagram:Pics/memory/byte-array-small.png]

Indexes are "memory addresses" (a.k.a. pointers)

Memory 34/82

Properties of physical memory

called main memory (or RAM, or primary storage, ...)
indexes are "memory addresses" (a.k.a. pointers)
data can be fetched in chunks of 1,2,4,8 bytes
cost of fetching any byte is same (ns)
can be volatile or non-volatile

When addressing objects in memory ...

any byte address can be used to fetch 1-byte object
byte address for N-byte object must be divisible by N

... Memory 35/82

Memories can be categorised as big-endian or little-endian

Exercise 7: Endianness 36/82

Write code to print out an int, byte by byte. Is your system big or little endian?

Data Representation

Data Representation 38/82

Ultimately, memory allows you to

load bit-strings of sizes 1,2,4,8 bytes
from N-byte boundary addresses
into registers in the CPU

What you are presented with is a string of 8,16,32,64 bits

Need to interpret this bit-string as a meaningful value

Data representations provide a way of assigning meaning to bit-strings

Character Data 39/82

Character data has several possible representations (encodings)

The two most common:

ASCII (ISO 646)
- 7-bit values, using lower 7-bits of a byte (top bit always zero)
- can encode roman alphabet, digits, punctuation, control chars
UTF-8 (Unicode)
- 8-bit values, with ability to extend to multi-byte values
- can encode all human languages plus other symbols
  (e.g. √ ∑ ∀ ∃ or )

ASCII Character Encoding 40/82

Uses values in the range 0x00 to 0x7F (0..127)

Characters partitioned into sequential groups

control characters (0..31) ... e.g. '\0', '\n'
punctuation chars (32..47,91..96,123..126)
digits (48..57) ... '0'..'9'
upper case alphabetic (65..90) ... 'A'..'Z'
lower case alphabetic (97..122) ... 'a'..'z'

Sequential nature of groups allows for things like (ch - '0') Eg. '4' - '0' converts the character '4' into the integer 4.

See man 7 ascii

Unicode 41/82

Basically, a 32-bit representation of a wide range of symbols

around 140K symbols, covering 140 different languages

Using 32-bits for every symbol would be too expensive

e.g. standard roman alphabet + punctuation needs only 7-bits

More compact character encodings have been developed (e.g. UTF-8)

UTF-8 Character Encoding 42/82

UTF-8 uses a variable-length encoding as follows

#bytes	#bits	Byte 1	Byte 2	Byte 3	Byte 4
1	7	`0xxxxxxx`	-	-	-
2	11	`110xxxxx`	`10xxxxxx`	-	-
3	16	`1110xxxx`	`10xxxxxx`	`10xxxxxx`	-
4	21	`11110xxx`	`10xxxxxx`	`10xxxxxx`	`10xxxxxx`

The 127 1-byte codes are compatible with ASCII

The 2048 2-byte codes include most Latin-script alphabets

The 65536 3-byte codes include most Asian languages

The 2097152 4-byte codes include symbols and emojis and ...

... UTF-8 Character Encoding 43/82

UTF-8 examples

ch	unicode	bits	simple binary	UTF-8 binary
$	U+0024	7	`010 0100`	`00100100`
¢	U+00A2	11	`000 1010 0010`	`11000010 10100010`
€	U+20AC	16	`0010 0000 1010 1100`	`11100010 10000010 10101100`
𐍈	U+10348	21	`0 0001 0000 0011 0100 1000`	`11110000 10010000 10001101 10001000`

Unicode strings can be manipulated in C (e.g. "")

Like other C strings, they are terminated by a 0 byte (i.e. '\0')

Warning: Functions like strlen may not work as expected.

Exercise 8: UTF-8 Unicode Encoding 44/82

For each of the following symbols, with their Unicode value

show the bit-string that would be used to represent them

Symbols:

& U+00026
µ U+000B5
✓ U+02713

Given that ♥ has the code U+02665

Write a C program to print
♥ beats

Numeric Data 45/82

Numeric data comes in two major forms

integer ... subset (range) of the mathematical integers
floating point ... subset of the mathematical real numbers

Integer Constants 46/82

Four ways to write integer constants in C

42 ...signed decimal (0..9)
0x2A ...unsigned hexadecimal (0..F)
052 ... unsigned octal (0 ..7)
0b1010 ... unsigned binary (0 ..1)

Variations

123U ... unsigned int value (typically 32 bits)
123LL ... long long int value (typically 64 bits)
123S ... short int value (typically 16 bits)

Invalid constants lie outside the range for their type, e.g.

4294967296, -1U, 666666S, 078 0b234

Unsigned integers 47/82

The unsigned int data type

commonly 32 bits, storing values in the range 0 .. 2³²-1

[Diagram:Pics/memory/unsigned-int-small.png]

... Unsigned integers 48/82

Value interpreted as binary number

E.g. consider an 8-bit unsigned int

01001101 = 2⁶ + 2³ + 2² + 2⁰ = 64 + 8 + 4 + 1 = 77

Addition is bitwise with carry

  00000001     00000001     01001101     11111111
+ 00000010   + 00000011   + 00001011   + 00000001
  --------     --------     --------     --------
  00000011     00000100     01011000     00000000

Most machines will also flag the overflow in the fourth example

Exercise 9: Hexadecimal ↔ Binary ↔ Decimal 49/82

When working at the machine level

as we will be with MIPS assembler
useful to know how to map between Hex/Decimal/Binary

Convert these 8-bit binary numbers to hexadecimal:

00001001, 00001101, 00101010, 00110011, 11001100

Convert these 8-bit binary numbers to decimal:

00001001, 00001101, 00101010, 00110011, 11001100

Convert the following decimal numbers to 8-bit binary:

15, 64, 99, 200, 256

Signed integers 50/82

The int data type

commonly 32 bits, storing values in the range -2³¹ .. 2³¹-1

[Diagram:Pics/memory/signed-int-small.png]

... Signed integers 51/82

Several possible representations for negative values

signed magnitude ... first bit is sign, rest are magnitude
ones complement ... form -N by inverting all bits in N
twos complement ... form -N by inverting N and adding 1

In all representations, +ve numbers have 0 in leftmost bit

Examples: representations of (8-bit) -5 (where 5 is 00000101)

10000101 ... signed magnitude
11111010 ... ones complement
11111011 ... twos complement

... Signed integers 52/82

Signed magnitude: Easy to form -X from X ... XOR in high-order bit

A problem (using 8-bit ints) ...

what do these numbers represent? 00000000, 10000000

Two zeroes ... one positive, one negative

Another problem: x + -x ≠ 0 (mostly) with simple addition

  00000011  3     00101010  42      01111111  127
+ 10000011 -3   + 10101010 -42    + 11111111 -127
  --------        --------          --------
  10000110 !0     11010100  !0      01111110   !0

To fix requires extra hardware in ALU (Arithmetic Logic Unit) in the CPU

... Signed integers 53/82

Ones complement: Easy to form -X from X ... NEG all bits

A problem (using 8-bit ints) ...

what do these numbers represent? 00000000, 11111111

Two zeroes ... one positive, one negative

At least x + -x is equal to one of the zeroes with simple addition

  00000011  3     00101010  42      01111111
+ 11111100 -3   + 11010101 -42    + 10000000
  --------        --------          --------
  11111111 -0     11111111  -0      11111111 -0

... Signed integers 54/82

Twos complement: to form -X from X ... NEG all bits, then add 1

Now have only one representation for zero (00000000)

-0 = ~00000000+1 = 11111111+1 = 00000000

Only one zero value. Also, -(-x) = x

Even better, x + -x = 0 in all cases with simple addition

  00000011  3     00101010  42      01111111
+ 11111101 -3   + 11010110 -42    + 10000001
  --------        --------          --------
  00000000  0     00000000   0      00000000  0

Always produces an "overflow" bit, but can ignore this

Exercise 10: Binary↔decimal Conversion 55/82

Convert these decimal numbers to 8-bit 2's complement binary:

15, -64, 127, 128

What decimal numbers do these 8-bit 2's complement represent:

11111111, 11010110, 10111101

Demonstrate the addition of x + -x, where x is

5, 127

Pointers 56/82

Pointers represent memory addresses/locations

number of bits depends on memory size, 64-bits on cse machines
data pointers reference addresses in data/heap/stack regions
function pointers reference addresses in code region

Many kinds of pointers, one for each data type, but

sizeof(int *) = sizeof(char *)
= sizeof(double *) = sizeof(struct X *)

... Pointers 57/82

Code and data is aligned and is machine dependant. For example:

char ... can be stored at any byte address
int ... must be stored at an address addr %4 == 0
double ... often must be stored at an address addr %8 == 0

Thus pointer values must be appropriate for data type, e.g.

(char *) ... can reference any byte address
(int *) ... must have addr %4 == 0
(double *) ... might need to have addr %8 == 0

Exercise 11: Valid Pointers 58/82

Which of the following are likely to be valid pointers

0x00000000   0x00001000   0x00001001
0x7f000000   0x7f000001   0x7f000004

to objects of the following types

[Diagram:Pics/clang/memory-regions-small.png]

Fractions in different Bases 59/82

The decimal fraction 0.75 means

7*10^-1 + 5*10^-2 = 0.7 + 0.05 = 0.75
or equivalently 75/10² = 75/100 = 0.75

Similary 0b0.11 means

1*2^-1 + 1*2^-2 = 0.5 + 0.25 = 0.75
or equivalently 3/2² = 3/4 = 0.75

Similarly 0x0.C means

12*16^-1 = 0.75
or equivalently 12/16¹ = 3/4 = 0.75

Note: We call the . a radix point rather than a decimal point when we are dealing with other bases.

... Fractions in different Bases 60/82

If we want to convert 0.75 in decimal to binary, it may be easy to look and and realise we need 0.5 + 0.25 which gives us 0b0.11. Sometimes it is not that easy and we need a systematic approach.

The algorithm to convert a decimal fraction to another base is:

take the fractional component and multiply by the base
the whole number becomes the next digit to the right of the radix point in our fraction.
We now disregard the whole number part of the previous result and repeat this process until the fractional part becomes exhausted or we have sufficient digits (this process is not guaranteed to terminate).

... Fractions in different Bases 61/82

For example if we want to convert 0.3125 to base 2

0.3125 * 2 = 0.625
0.625 * 2 = 1.25
0.25 * 2 = 0.5
0.5 * 2 = 1.0

Therefore 0.3125 = 0b0.0101

Exercise 12: Fractions: Decimal → Binary 62/82

Convert the following decimal values into binary

12.625
0.1

Floating Point Numbers 63/82

Floating point numbers model a (tiny) subset of ℝ

many real values don't have exact representation (e.g. 1/3)
numbers close to zero have higher precision (more accurate)

C has two floating point types

float ... typically 32-bit quantity (lower precision, narrower range)
double ... typically 64-bit quantity (higher precision, wider range)

Literal floating point values: 3.14159, 1.0/3, 1.0e-9

printf("%10.4lf", (double)2.718281828459);
displays ⎵⎵⎵⎵2.7183
printf("%20.20lf", (double)4.0/7);
displays 0.57142857142857139685

... Floating Point Numbers 64/82

IEEE 754 standard ...

scientific notation with fraction F and exponent E
numbers have form F × 2^E, where both F and E can be -ve
INFINITY = representation for ∞ and -∞ (e.g. 1.0/0)
NAN = representation for invalid value (e.g. sqrt(-1.0))

Fraction part is normalised (i.e. 1.2345×10² rather than 123.45)

In binary, exponent is represented relative to a bias value B

if the unsigned exponent value is e, the actual value is e-B

... Floating Point Numbers 65/82

Example of normalising the fraction part in binary:

1010.1011 is normalized as 1.0101011×2⁰¹¹
1010.1011 = 10 + 11/16 = 10.6875
1.0101011×2⁰¹¹ = (1 + 43/128) * 2³ = 1.3359375 * 8 = 10.6875

The normalised fraction part always has 1 before the decimal point.

Example of determining the exponent in binary:

assume an 8-bit exponent, then bias B = 2^8-1-1 = 127
valid bit patterns for exponent 00000001 .. 11111110 (1..254)
exponent values -126 .. 127

... Floating Point Numbers 66/82

Special cases:

If every bit (except the sign bit) is 0 then we have the number 0. This means we can have positive and negative 0.
If every bit of the exponent is 1 and the fraction is 0 then we have infinity (positive or negative)
If every bit of the exponent is 1 and the fraction is not 0 then we have NaN (not a number).
Underflow: If the exponent has minimum value (all zero), special rules for denormalized values are followed. The exponent value is set to 2^-126 and the "invisible" leading bit for the fraction part is no longer used.

... Floating Point Numbers 67/82

Internal structure of floating point values

[Diagram:Pics/memory/float-rep-small.png]

More complex representation than int because 1.dddd e dd

... Floating Point Numbers 68/82

Example (single-precision):

150.75 = 10010110.11
         // normalise fraction, compute exponent
       = 1.001011011 × 2⁷
         // determine sign bit,
         // map fraction to 24 bits,
         // map exponent relative to baseline
       = 0100000110001011011000000000000000

where red is sign bit, green is exponent, blue is fraction

Note: B=127, e=2⁷, so exponent = 127+7 = 134 = 10000110

Exercise 13: Floating point ↔ Decimal 69/82

Convert the decimal numbers 1 to a floating point number in IEEE 754 single-precision format.

Convert the following floating point numbers to decimal.

Assume that they are in IEEE 754 single-precision format.

0 10000000 11000000000000000000000

1 01111110 10000000000000000000000

You can try out more examples with this Floating Point Calculator

Arrays 70/82

Arrays are defined to have N elements, each of type T

Examples:

int    a[100];    // array of 10 ints
char   str[256];  // array of 256 chars
double vec[100];  // array of 100 doubles

Elements are laid out adjacent in memory

[Diagram:Pics/memory/array-in-mem-small.png]

... Arrays 71/82

Assuming an array declaration like Type v[N ] ...

individual array elements are accessed via indices 0..N-1
total amount of space allocated to array N × sizeof(Type )
array name gives address of first element (e.g. v = &v[0])
array indexing can be treated as v[i] ≅ *(v+i)

Strings are just arrays of char with a '\0' terminator

constant strings have '\0' added automatically
string buffers must allow for element to hold '\0'

... Arrays 72/82

When arrays are "passed" to a function, actually pass &a[0]

[Diagram:Pics/memory/string-param-small.png]

... Arrays 73/82

Arrays can be created automatically or via malloc()

int main(void)
{
    char str1[9] = "a string";
    char *str2;  // no array object yet

    str2 = malloc(20*sizeof(char));
    strcpy(str2, str1);
    printf("&str1=%p, %s\n", &str1, str1);
    printf("&str2=%p, %s\n", &str2, str2);
    printf("str1=%p, str2=%p\n",str1,str2);
    free(str2);
    return 0;
}

Two separate arrays (different &'s), but have same contents

(except for the unitialised parts of the arrays)

Structs 74/82

Structs are defined to have a number of components

each component has a Name and a Type

Example:

[Diagram:Pics/memory/struct-student-small.png]

... Structs 75/82

To ensure alignment for the fields and for the struct itself, internal "padding" may be needed

[Diagram:Pics/memory/struct-pad-small.png]

Padding wastes space; You can try to re-order fields to minimise waste.

Unions 76/82

A union is a special data type available in C that allows storing different data types in the same memory location.

The size of a union is equal to the size of its largest member (plus any padding).

An example of declaring a union

union MyUnion {
    unsigned long long value;
    char   s[8];
};

This union can store either an unsigned long long value, or a string of size 8 (including the '\0' terminator).

... Unions 77/82

Example usage

union MyUnion u;
printf("%d\n",sizeof(union MyUnion)); prints out 8 
u.value = 999999;
printf("%llu\n",u.value); prints out 999999 
strcpy(u.s,"hello");
printf("%s\n",u.s);       prints out hello 
printf("%llu\n",u.value); Does NOT print out 999999 
                          as it has been (partly) overwritten

... Unions 78/82

Common use of union types: "generic" variables

#define IS_INT   1
#define IS_FLOAT 2
#define IS_STR   3

struct generic {
   int   vartype;
   union { int ival; char *sval; float fval; };
} myVar;

// treat myVar as an integer
myVar.vartype = IS_INT;
myVar.ival    = 42;
printf("%d\n", myVar.ival);
// now treat myVar as a float
myVar.vartype = IS_FLOAT;
myVar.fval    = 3.14159;
printf("%0.5f\n", myVar.fval);

Exercise 14: Union 79/82

What would be output if we did the following:

struct generic myVar;

// treat myVar as ???
myVar.vartype = IS_INT;
myVar.fval    = 3.14159;
printf("%d\n", myVar.ival);

// treat myVar as ???
myVar.vartype = IS_FLOAT;
myVar.ival    = 42;
printf("%0.5f\n", myVar.fval);

Bit Fields 80/82

We can specify size (in bits) of structure and union members.

struct date{
   //day has value between 1 and 31
   //so 5 bits are sufficient
   unsigned int day: 5;
   //month has value between 1 and 12, 
   //so 4 bits are sufficient 
   unsigned int month: 4;
   unsigned int year;
};

int main(void) {
   printf("%lu bytes\n", sizeof(struct date));
   struct date d = {31, 12, 2014};
   printf("%d/%d/%d", d.day, d.month, d.year);
   return 0;
}

... Bit Fields 81/82

Warnings when using bit-fields:

Little endian and big endian systems will lay out the bits in different ways. This can result in non-portable code in some situations
You can't have a pointer to a bit-field member as they may not start on a byte boundary

Eg The following won't compile

int main(void) {
   printf("%p\n", &(d.day));
   return 0;
}

Exercise 15: Bit-fields 82/82

What do you think the following will do? How can we fix it?

struct time{
    int hours: 5;
    int mins: 6;
    int secs: 6;
};
int main(void){
    struct time t = {22,12,20};
    printf("%d:%d:%d\n",t.hours,t.mins,t.secs);
    return 0;
}

Produced: 26 Apr 2019