22.txt

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

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

Today: Chapter 10 continued: bit manipulations, and enumerations
       Chapter 11: file I/O (in 23.txt)
Review: 
- bitwise-AND with bit vector V: 
  V can be used as a "mask"
  1 => pass through
  0 => force to 0
- bitwise-OR with bit vector V:
  V can be used to "force turn on" a bit
  1 => force it to turn on
  0 => pass through

A. How to "test" if bit [i] in a bit vector is either
  "set" (has value of 1) or
  "not set" (has value of 0)?

- answer: use AND operation with a generated mask.
  and use (wordwise) logical operators 

Example: to test bit 3 in a big-endian vector V, we can do

	V & 0x00000008
 Why? because 8 is 1000 in binary, 
 and the result of this V expression can be only two possible value:
	0x0  if bit 3 of V is zero
	0x8  if bit 3 of V is one

Control statements (if/while/..) use either 0 or non-zero for false/true.
To convert this to zero/one, you can also just use the
! (logical negate) operator twice:
  once to force to 0 or 1 (in negated polarity)
  once to convert back to the true polarity

However, the question asks for bit-i, not just bit-3.
Solution: use a (left) shift expression:

	V & (1 << i)

This is because
i    1 << i
0    0x00000001    (that is ... 0001 binary)
1    0x00000002    (that is ... 0010 binary)
2    0x00000004    (that is ... 0100 binary)
3    0x00000008    (that is ... 1000 binary) etc

B. How to "set" or "clear" bit [i] in a bit vector?
   set means assign 1 to the bit
   clear means assign 0 to the bit

- answer:
  To set: OR 1 in the position to set,
          OR 0 in other positions not affected
  To clear: AND 0 in the position to clear,
            AND 1 in other positions unaffected.

Example: to set bit 3 in V,
	V = V | 0x00000008;
  (because OR 1 will force that bit to be on, OR 0 will pass the original bit)
To clear bit 3 in V, 
	V = V & 0xfffffff7;
  (because AND 0 will force that bit to be 0, AND 1 will pass the original bit)

Generalize the mask to bit i:
- To set
	V = V | (1 << i);
- To clear
	V = V & ~(1 << i);

How to complement bit i in a bit vector V?
  (complement means change 0 to 1, change 1 to 0)
- Answer: use XOR 1
  because XOR 0 means pass original bit through, XOR 1 means complement.
	V = V ^ (1 << i);

All bit level operations have the "incremental assignment" form
	V &= (1 << i)  is the same as V = V & (1 << i)
	|= for bitwise OR
	^= for bitwise XOR
	<<= for left shift
	>>= for right shift
 etc

Bit fields
- this is a way to declare "slices" of a bit vector
  using syntax similar to structures.

Example
	struct bitCard {
		unsigned face: 4;
		unsigned suit: 2;
		unsigned color: 1;
	};

This is similar to a structure, except the fields occupy part of a word.

The syntax for bit field is just like a struct except the additional 
	:4    for 4-bits
	:2    for 2-bits
	etc
In this case, the whole struct can fit in a single word (like bit vector)
When you print
	sizeof(struct bitCard)
most like you get
	4
because it fits in one word (int)!

Layout of bit fields in a word: compiler dependent.
It could be just left-to-right order
	face: 4 => bits 31 to 28
	suit: 2 => bits 27 to 26
	color: 1=> bit 25

Suppose V is a bit vector that is used to implement a struct bitCard.
Then,
To extract value V.face and assign to a variable C,
- shift V to the right (by 28 bits) 
  apply bit mask to extract the field
	C = (V >> 28) & 0xf;

To assign value F (as an int or unsigned) to V.face:
- create a bit mask to extract bits 
  shift F to the left (by 28 bits) to align with the bit field,  
	temp1 = (F & 0xf) << 28;
- create a bit mask to extract bits 27--0 of V
	temp2 = (V & 0x0fffffff);
- take bit OR of these two values
	V = temp1 | temp2;

Reason for using bit field: to save space.
without using bit fields, it would take 4 bytes per field,
for a total of 4 * 3 = 12 bytes each!

you can use bit-fields just like any struct.  Actually, the 
compiler should let you pass it as the type you declared:
	printf("%u\n", V.card);
it would automatically extract the card field, convert to the
declared type of card, and pass it as a parameter (R-value).

However, you pay a price:

1. it is potentially slower, because it takes multiple operations
2. you can't apply address-of operators on bitfield!
   Because it is not a byte address.
   You can't say
   scanf("%d", &V.card);
   You have to save it in a variable and then assign it.
   (it has a restricted, "synthesized" L-value)

More about bit fields:
- you can actually define your own padding using "unnamed bit fields"
  but this is very compiler-dependent

struct example {
	unsigned a: 13;
	unsigned  : 19;  /* this has no name! */
	unsigned b: 4;
};

the 19 bits are unused for storage; it is to force separation
between the bit fields.

struct example2 {
	unsigned a: 13;
	unsigned  : 0; /* this means let compiler choose alignment */
	unsigned b: 4; 
};

0 doesn't mean skip 0 bits; it means let compiler decide
(usually byte boundary)

---
more on enum types:
- by default, enum constants are assigned values 0, 1, 2 ... 
- example
	enum Months {
		JAN, FEB, MAR, APR, MAY, JUN, JUL, AUG, SEP, OCT, NOV, DEC
	};
  JAN has value 0, FEB has value 1, etc
- possible to override the int value
  e.g., might want JAN to be 1, FEB to be 2, etc
	enum Months {
		JAN = 1, FEB, MAR, APR, MAY, ...
	};
  JAN = 1 overrides the default of 0,
  and subsequent ones increment by 1 automatically