Unit 1a - Numbers and Memory

• Memory

  • stores data encoded as bits
  • program instructions and state (variables, objects, etc.)

• CPU

  • reads instruction and data from memory
  • performs specified computation and writes result back to memory

• Example

  • C = A + B
  • memory stores: add instruction, and variables A,B, and C
  • CPU reads instruction and values of A and B, adds values and writes result to C

• Naming

  • unit of addressing is a byte (8 bits)

  • every byte of memory has a unique addresss

  • some machines have 32-bit memory addresses, some have 64

    • For this course, we will assume our machine have 32

• Access

  • lots of things are too bit to fit in a single byte

    • unsigned numbers > 255, signed numbers < -128 or > 127, most instructions, etc

  • CPU access memory in continguous, power of two size chunks of bytes.

• address of a chunk is address of first byte

Numbers and Human

• Sometimes we are interested in the integer value of chunk of bytes

  • Base 10, decimal, is natural for this

• Sometimes we are more interested in bits themselves, so we use base-2, binary

  • a small 256-byte memory has addresses 0₂ to 11111111₂
  • but, as addresses get bigger, this gets tedious

• Once we used base-8, octal

  • 64-KB memory addresses go up to 1111111111111111₂ = 177777₈

• Once we use base-16, hexadecimal

  • 4-GB memory addresses go up to 377777777₈ = ffffffff₁₆

    • if you don't have subscripts, ffffffff₁₆ is written as 0xffffffff

Binary $\leftrightarrow$ Hex is Easy!

• How many bits in a hexc "digit", a hexit?

• Consider ONE hexit at a time: $8 \times i_4 + 4 \times i_3 + 2 times i_2 + 1 \times i_1$

  6 a 5 5 0 e a 3

• A byte is just 2 hexadecimal digits:

  0x6a 0x55 0x0e 0xa3 => 0x6a550ea3

Operations on Hex Numbers

• We use hex for addresses

  • We don't really care what their base-10 value is

• Addition/subtraction in hex

  • You could convert both to decimal, but that might be too hard.
  • You can calculate in hex directly
  • Alternative for subtraction: use addition with two's complements

• Remember that:

  • carry is $0x10 == 16$
  • $a..f$ convert to their decimal values

Subtracting in Hex

• Object A is at address 0x10d4, and object B is at 0x1110. They are stored contiguously in memory (i.e., they are adjacent to each other). how big is a?

• Address B - Address A = Size of A

Making Integers from Bytes

• First architectural decision:

  • assembling memory bytes into integers

• Consider a 32-bit integer (int in Java or C)

  • It uses 4 bytes
  • If memory address is i, then we also need i+1, i+2, i+3
  • Example: if address is 0x2014, then integer is in 0x2014, 0x2015, 0x2016, 0x2017

• What do each of these bytes represent?

Big Endian

• We can start at the "big end"

  • In other words, the first byte is the most significant one

• Example, to store the number 0x12345678:

  • Most significant byte is 0x12 (bits 24 to 31), so its stored first.

Little Endian

• We can start at the "little end"

  • In other words, the first byte is the least significant one
  • Used in most Intel-based systems

• Example, to store the number 0x12345678:

  • Least significant byte is 0x78(bits 0 to 7), so it's stored first

Address Alignment

• What is an "aligned" address?

  • Address whose number is a multiple of the object size

• Aligned addresses are better:

  • You can fit two shorts inside an int, etc.
  • This is significant in arrays as well
  • Some CPUs don't support misaligned addresses
  • Intel: misaligned access is slower

• CPU Implementation encourages alignment

  • Memory is organized internally into chunks (blocks)
  • Every memory access requires accessing a whole block

• CPU memory access looks liek:

  • Read/write $N$ bytes starting at address $A$

• This is translated by memory to:

  • Block $B$ contains addresses $X .. ( X+ \text{blocksize} - 1)$
  • $X \leq A \leq X + \text{blocksize} - 1$
  • Read/write $N$ bytes starting at $0^{th}$ byte of block $B (A = X + 0)$

• So:

  • Block $B$ contains addresses $X .. (X + \text{blocksize} - 1)$
  • $X \leq A \leq X + \text{blocksize} - 1$
  • Read/write $N$ bytes starting at $0^{th}$ byte of block $B (A = X + 0)$

• How is this simplified if:

  • $\text{blocksize}$ is a power of 2
  • $X$ and $N$ are powers of 2
  • $A$ is aligned to $N$?

Changing Data Types: Extending

• Extending an integer: increasing the number of bytes used to store it

 
2
1
byte b = -6 // stored as 11111010
2
int i = b;  // stored as 11111111111111111111111111111010

• Signed extension: used in signed data types

  • Everything is signed in Java
  • Copy first bit (sign) to extended bits

• Zero extension: used in unsigned data types (C)

  • Set all extended bits to zero
  • How to do it in Java?

Changing Data Types: Truncating

• Truncating an integer: reducing the number of bytes used to store it:

 
2
1
int i = -6; // stored as 11111111111111111111111111111010
2
byte b = i; // stored as stored as 11111010

• What could go wrong?

  • What value would b get if i were 256? or 128?

    • big negative value

• Java warns you if you truncate implicity

  • To avoid warning, cast explicity:

    byte b = (byte) i

Bit Operations in C / Java

• a << b: shift all bits in a to the left b times, fill remaining right bits with zero

• a >> b: shift all bits in a to the right b times

  • C: if a is unsigned, fill with zeros (zero-extend), otherwise fill with first bit of a (sign-extend)
  • Java: operator >> sign-extends, operator >>> zero-extends.

• a & b : AND applied to corresponding bits in a and b

• a | b : OR applied to corresponding bits in a and b

• a ^ b : XOR applied to corresponding bits in a and b

• ~a: inverts every bit of a

Making Use of Bit Operations

• Shifting multiplies / divides by power of 2

  • a<<b is equivalent to $a \times 2^b$
  • a>>b is equivalent to $\frac{a}{2^b}$

• Example: 22 in binary is 00010110

  • 11 is 00001011 (22 shi ft right once, $\frac{22}{2^1}$)
  • 44 is 00101100 (22 shifted left one, $22 \times 2^1$)
  • 88 is 01011000 (22 shifted left twice, $22\times2^2$)

• Works for negative numbers too, if using sign-extended shift

• Review:

   
  2
  1
  byte b = -6; // stored as 11111010
  2
  int i = b;   // stored as 1111...1111 11111010
  

• How can we get it to zero-extend instead of sign-extend?

• Answer: using bit operations:

   
  2
  1
  // 0xFF in bits is: 0000…000011111111
  2
  int u = b & 0xFF; // stored as 0000…000011111010
  

  ​