# 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*). - All possible addresses form the
*virtual address space*.

### 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:

For conversion from unsigned integer to signed integer:

### 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:

To truncate an two’s complement number:

### 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 |