CSAPP Walk Through: Chapter 2

Posted by Shawn Ding on May 12, 2015

These series of notes are based on the book Computer Systems: A Programmer’s Perspective.

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