21.txt

一個計算機系教授的上課講義 主要是教導學生使用C語言編寫程序

CS 1355
Introduction to Programming in C
Monday 2006.11.27
Lecture notes (at http://r638-2.cs.nthu.edu.tw/C/notes/21.txt)

Today: Chapter 10: C structures, unions, bit manipulations

What is a structure ("struct")?
- struct is a keyword
- struct is for declaring a "multi-part" data type
  - previously, had int, char, float, double, ...
  - array = multiple units of the same type
  - struct: mix and match different data types in one container
- a struct is sometimes called a "record" in other programming languages

Example: a card
- has a face (♤♢♧♡) and a suit (A23456789JQK)
- several ways to declare this:

## First Way ##
struct Card {
	char *face;
	char *suit;
};

=> this declares "Card" as a "structure tag".
   it is almost the name of a tag, but it is not!
Note: field names are "local to" (scoped inside) the type.
  => face, suit are not visible without the struct (container)!

To declare a variable using this type tag, you have to say

	struct Card x;

=> this declares x as a variable of type "struct Card"
=> x has two "fields", namely "face" and "suit"
=> a "field" is also called a "structure member"
   - they are like two sub-variables of x
   - x is like a container of these fields

Once you have the variable, you can say
	x.face = "spade";
	x.suit = "queen";

Array initializer works also:
	struct Card x = {
		"spade", /* this is for the .face field */
		"queen"   /* this is for the .suit field */

## Second way ##
typedef struct {
	char *face;
	char *suit;
} CardType;

=> This declares "CardType" as the name of a type.
   In this case, it does not use a type tag.
To declare a variable using this type name, you just say

	CardType x;

=> this declares x as the structure type.
   structurally, it is just like the previous way
	x.face = "spade"; ... etc

Pointers with structs:
If you want a pointer, just declare
	struct Card *p; or
	CardType    *q;

Pointers can point to other structures.  
- You have to use & operator to get "address of"!!
- struct expressions have L-value
- struct expressions are not pointers (whereas arrays are)

	p = &x;  /* pointer p gets address of struct x */

To access a field from a struct pointer, there are two ways
1) 	(*p).face = "diamond";
2)	p->suit = "king";

Note: you must use (*p).face, because * has lower precedence!
     *p.face is same as *(p.face)!
     but since p is a pointer, p.face is an error
- Almost everybody uses the -> syntax

What is the purpose of using a struct-tag???
=> for recursive data structures!
=> But, the recursive field must be a pointer, not another struct!
Reason: if a data structure "contains" (instead of "references")
  another copy of its own type, then it will be infinitely large!

For example,

struct Person {
	char name[30];
	int age;
	struct Person  *father, *mother;
};

This way, I can say

	struct Person me, mom, dad;
	me.father = &dad;
	me.mother = &mom;

Comparison:
- you CANNOT use comparison operators on structs (as R-value)!
  example: suppose both personA, personB are of type (struct Person)
	if (personA != personB) { ... } => this won't work!! syntax error
	personA > personB
	personA < personB
	personA == personB, etc... all bad
- But, it's ok to do pointer comparison
  example, suppose you have  struct Person *P1, *P2;
  then ok  to say
	if (P1 == P2) { printf("P1 and P2 are the same person!\n"); }
	   P1 != P2
   but can't use <  >  <=  >= to compare pointers 

sizeof a struct:
- there might be surprises when you call sizeof on a struct 
  => might be bigger than you think!
  => reason: alignment of fields to word boundaries
struct example { 
	char c;
	int i;
};
printf("%d\n", sizeof(struct example));
=> this prints 8  (on most systems)
=> reason: char c might be 1 byte, 
   but int i must start on an int boundary (for efficiency reason)
   so, some space between c and i are "wasted"

Assignment:
- structs may be assigned!
	struct Card x, y = { "diamond", "jack" };
	x = y; /* this is ok! */
	/* this effectively does 
		x.face = y.face;
		x.suit = y.suit;
	 */
- It does not require like a strcpy() function

Passing parameters:
- structs are passed by value!
  Reason: struct expression itself is not an "address" like an array,
          but is an R-value of the struct
  => it passes a copy as a parameter
  => modifying the parameter does not affect the original
- also possible to pass pointer, using "address of" operator &
- This means, if you have an array inside a struct, 
  the array gets passed by value!!
 Example from before
	struct Person {
		char name[30]; /* <== this gets passed by value if inside struct */
	};

Return value:
- yes you can return a struct!
  actually you have to declare a local variable,
  and then return (the R-value) of that variable (by value)
- it makes a copy of the value, not a reference to an auto-variable

Example:
#include <random.h>
char *suit[] = { "Hearts", "Diamonds", "Clubs", "Spades" };
char *face[] = { "Ace", "Two", ..., "Jack", "Queen", "King" };

struct Card
getRandomCard() {
	struct Card c;
	c.suit = suit[rand() % 4];
	c.face = face[rand() % 13];
	return c;
};

This way you can return a random card
	struct Card x = getRandomCard();
=> this is copied to x field-by-field

book example: shuffle cards
- previously: using 2D array of int, assign card order 1..52
- this time: use struct
	wDeck[ ] is the deck of cards
(1) initialize the records
void fillDeck(Card wDeck[], const char *wFace[], const char *wSuit[]) {
	int i;
	for (i=0; i<52; i++) {
		wDeck[i].face = wFace[i % 13]; /* index is 0..12 */
		wDeck[i].suit = wFace[i / 13]; /* index is 0..3 */
	}
}
=> after the call, cards are in "sorted order"

(2) shuffle: 
  go through one card at a time, swap with a random position

void shuffle(Card wDeck[ ]) {
	int i, j;
	Card temp;
	for (i = 0; i < 52; i++ ) {
		j = rand() % 52; /* pick a random position to swap with */
		temp = wDeck[i];
		wDeck[i] = wDeck[j];
		wDeck[j] = temp;
	}
}

======
Unions
- what's a union?
- union is just like a struct, except the fields all occupy the same space
Try it:

#include <stdio.h>
union number {
	int i;
	float f;
	char c[4];
};
int main() {
	union number u;
	int i;
	printf("enter int: "); /* prompt */
	scanf("%i", &u.i);     /* get int into union */
	printf("bytes are %02x %02x %02x %02x\n", u.c[0], u.c[1], u.c[2], u.c[3]);
}

=> This lets you to see what individual bytes look like.

If you run on PowerPC, Sun Sparc, 68K, ...
enter int: 13
bytes are 00 00 00 0d

But if you run on Intel x86 (Pentium, Core Duo, ...)
bytes are 0d 00 00 00

why? 
because of "Endian" difference of the CPUs!
- Intel is "little endian" (least-significant byte first)
- Virtually everybody else is "big endian" (most-significant byte first)
- some have configurable endians (software controllable)

0x12345678 would be printed as 
12 34 56 78 => on big endian
78 56 34 12 => on little endian

Can use this to look at data of different sizes, floats, double etc

Bitwise Operators
- logical operator, applied to each bit of the same position
- Truth tables (for each bit)
a  b   a & b  (logical-AND)
-------------
0  0     0
0  1     0
1  0     0
1  1     1

a  b   a | b    (logical-OR)
-------------
0  0     0
0  1     1
1  0     1
1  1     1

a  b   a ^ b    (logical-XOR) "exclusive-OR"
-------------
0  0     0
0  1     1
1  0     1
1  1     0

a   ~a         (bit complement)
-------
0    1
1    0

However, each word is 32 bits
=> this means the bitwise operator is applied to 32 pairs of bits!!

What is the value of  0x12345678 & 0xabcdef90 ?
- translate to binary: 
  0x12345678 = 0001 0010 0011 0100 0101 0110 0111 1000
  0xabcdef90 = 1010 1011 1100 1101 1110 1111 1001 0000
           & = 0000 0010 0000 0100 0100 0110 0001 0000
             =0x  0    2    0    4    4    6    1    0  = 0x02044610

What is the value of  0x12345678 | 0xabcdef90 ?
- translate to binary: 
  0x12345678 = 0001 0010 0011 0100 0101 0110 0111 1000
  0xabcdef90 = 1010 1011 1100 1101 1110 1111 1001 0000
           | = 1011 1011 1111 1101 1111 1111 1111 1000
             =0x  b    b    f    d    f    f    f    8  = 0xbbfdfff8

What is the value of  0x12345678 ^ 0xabcdef90 ?
- translate to binary: 
  0x12345678 = 0001 0010 0011 0100 0101 0110 0111 1000
  0xabcdef90 = 1010 1011 1100 1101 1110 1111 1001 0000
           & = 1011 1001 1111 1001 1011 1001 1110 1000
             =0x  b    9    f    9    b    9    e    8  = 0xb9f9b9e8

What is the value of ~0x12345678?
  binary is complement of 
     0001 0010 0011 0100 0101 0110 0111 1000
 =>  1110 1101 1100 1011 1010 1001 1000 0111
 = 0x   e    d    c    b    a    9    8    7            = 0xedcba987

Other example: 
~0  is 0xffffffff

Important distinction between 
- wordwise logical operators, vs
- bitwise logical operators

wordwise: whole 32 bits are treated as one logical value (either 0 or not zero)
          &&    ||    !
bitwise:  every bit is a value. you get parallel operations
          &      |     ~

In general-purpose computers, 
- you get bytes as smallest "addressable" data size
- CPU actually manipulates everything as words (ints, 32 bits) at a time
- no bit memory; all bits are part of bytes or words

"bit vectors": array of single bits
- an in can be used as an array of 32 bits!
- however, C syntax does not support bit addressing
 (other language might, e.g., verilog has   bv<20>  => for bit 20 of bit vector bv)
 
Application: use bit vector to represent "set" (集合)
  e.g., the mathematical set { 1, 3, 9, 12, 15, 27 } can be represent using 
     bit vector   0000 1000 0000 0000 1001 0010 0000 1010
     (bit positions    27,           15,12,  9,      3,1)
- union of two sets = bitwise OR operation on the bit vectors
- intersection of two sets = bitwise AND

How to handle
- set subtraction?  (note: the following is math syntax, not C syntax)
  e.g., if S = { 1, 3, 5, 7, 9 }, T = { 2, 7, 8, 9 }
        S - T (sometimes written as S \ T) = { 1, 3, 5 }
  Answer:  ( S & (~T))
  How:    S = 0000 0000 0000 0000 0000 0010 1010 1010
         ~T = 1111 1111 1111 1111 1111 1100 0111 1011
     S & ~T = 0000 0000 0000 0000 0000 0000 0010 1010 = { 1, 3, 5 }
  Reason: 
    AND 1 => keep the bit (if it is available). i.e., "pass through"
    AND 0 => force the bit to 0                 i.e., "mask out"

- how to selectively complement a bit vector?
  Answer: use xor
    XOR 1 => complement the other bit
    XOR 0 => pass the other bit through

Shift bit operators
three kinds:
- shift left
     0x12345678 << 8  
     => shifts the bit vector 0x12345678 by 8 bits to the left,
        fill in 0 on the right end
     => has the value of  0x34567800   (throw away the hex 12 part, fill in 00)
- shift right logically
     (unsigned) 0x12345678 >> 8
     => shifts the bit vector by 8 bits to the right, 
     => it should be an unsigned bit vector
        fill in 0 on the left end
     => has the value of  0x00123456  (throw away hex 78 part, fill in 00)
- shift right arithmetically
  - treat the leftmost bit as the "sign bit"
  Number representation
  signed    as hex
    0       0x00000000
    1       0x00000001
   -1       0xffffffff    (all 1's)
   -2       0xfffffffe
   So, leftmost bit is used as the "sign" (0 = non-negative, 1 = negative)
  Arithmetic shift will fill in the sign bit!!
  examples
    0x87654321 >> 16   gives you  0xffff8765
  Why? because as binary,
    1000 0111 0110 0101 0100 0011 0010 0001
      8    7    6    5    4    3    2    1
      f    f    f    f    8    7    6    5   fill in 1 because sign bit is 1
  If the sign bit is 0, then fill in 0 on the left
  example
     0x1a2b3c4d >> 8   gives you  0x001a2b3c 
(to be continued)