# CSAPP Walk Through: Chapter 2

These series of notes are based on the book Computer Systems: A Programmer's Perspective. The homepage for the book is http://csapp.cs.cmu.edu/.

I put these notes here for me to review the book conveniently, hope it helps you as well.

## Imformation Storage

### Bytes

• Byte is the smallest addressable unit of memory.
• Every byte of memory is identified by a unique number(address).

### Words

• Word size indicates the nominal size of integer and pointer data.
• For a machine with a $w$-bit word size, the virtual memory addresses can range from $0$ to $2^w-1$.

### Data Sizes

This chart shows sizes of C numeric data types of 32-bit and 64-bit machines.

C declaration 32-bit 64-bit
char 1 1
short int 2 2
int 4 4
long int 4 8
long long int 8 8
char * 4 8
float 4 4
double 8 8

### Strings

• A string in C is encoded by an array of characters terminated by the null character(\0).

### Boolean Algebra

• Claude Shannon was the first to made the connection between Boolean algebra and digital logic.
• ** Opeartions: ** NOT, AND, OR and EXCLUSIVE-OR.

### Integer representations

To represent positive-only values(unsigned numbers), we use unsigned encodings. To represent both positive and negative values(signed numbers), we use two's complement encodings.

• U: Unisigned Encodings
• T: Two's Complement Encodings

Remember:

• $U_{Max} = 2^w - 1$
• $T_{Max} = 2^{w-1} - 1$
• $T_{Min} = 2^{w-1}$

### Conversions Between Signed and Unsigend

For conversions between signed and unsigned numbers with the same word size: the numeric values might change, but the bit patterns do not.

When executing an operation between an unsigned operand and a signed operand, C will convert the signed operand to an unsigned operand implicitly.

For conversion from signed integer to unsigned integer:

$$\begin{cases} x+2^w, & x < 0 \\\\ x, & x \ge 0 \end{cases}$$ For conversion from unsigned integer to signed integer: $$\begin{cases} -2^w + u, & u \ge 2^{w-1} \\ u, & u < 2^{w - 1} \end{cases}$$

### Expanding the Bit Representation of a Number

• Zero Extension: To expand a unsigned number, we simply add leading zeros to the representation.
• Sign Extension: To expand a two's complement number, we add copies of the most significant bit to the representation.

### Truncating Numbers

To truncate an unsigned number:

$$B2U_k\left(\left[x_{k-1}, x_{k-2}, ..., x_0\right]\right) = B2U_w\left(\left[x_{w-1}, x_{w-2}, ..., x_0\right]\right) \text{mod} ~ 2^k$$

To truncate an two's complement number:

$$B2T_k\left(\left[x_{k-1}, x_{k-2}, ..., x_0\right]\right) = U2T_k\left(B2U_w\left(\left[x_{w-1}, x_{w-2}, ..., x_0\right]\right) \text{mod} ~ 2^k\right)$$

### Floating Point

The numerical form of floating point numbers is $V_{10} = \left(-1\right)^s \cdot M \cdot 2^E$.

• Sign bit s determines whether the number is positive or negative.
• M is a fractional value in range $\left[1.0, 2.0\right]$
• E weights value by a power of 2.

Floating point in memory:

• Single precision(32 bits): 1 sign bit, 8 exponent bits and 23 fraction bits.
• Double precision(64 bits): 1 sign bit, 11 exponent bits and 52 fraction bits.

exponent bits encodes E, fraction bits encodes M.

Special values:

• When exp bits are all 1 and frac bits are all 0, the number represents $\infty$ ($+\infty$ when $s=0$ and $-\infty$ when $s=1$).
• When exp bits are all 1 and frac bits are not all 0, the number represents $NaN$(Not a Number).

Encoding:

• Exponent was coded as biased values: $E = exp - Bias$.
• Significand coded with implied leading 1: $M = 1.xxx...x$.

Example:

float f = 12345.0;

$12345_{10} = 1.1000000111001_2 \cdot 2^{13}$

Significand:

• $M = 1000000111001_2$.
• $frac = 10000001110010000000000_2$.

Exponent:

• $E = 13$
• $Bias = 127$
• $exp = E + Bias = 140 = 10001100_2$

Result:

sign bit exp frac
0 10001100 10000001110010000000000