2020 – Winter Term 2
Unit 1a – Numbers and Memory
1
CPSC 213 2020 ST1 © 2020 Jonatan Schroeder
▪ Reading
▪ Companion: 2.2.2
▪ Textbook: 2.1 – 2.3
▪Learning Objectives
▪ know the number of bits in a byte and the number of bytes in a short, long and quad
▪ determine whether an address is aligned to a given size
▪ translate between integers and values stored in memory for both big- and little- endian machines
▪ evaluate and write Java expressions using bitwise operators (&, |, <<, >>, and >>>)
▪ determine when sign extension is unwanted and eliminate it in Java
▪ evaluate and write C expressions that include type casting and the addressing operators (& and *)
▪ translate integer values by hand (no calculator) between binary and hexadecimal, subtract hexadecimal numbers and convert small numbers between binary and decimal
CPSC 213 2020 ST1 © 2020 Jonatan Schroeder 2
▪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
CPSC 213 2020 ST1 © 2020 Jonatan Schroeder 3
CPSC 213 2020 ST1 © 2020 Jonatan Schroeder 4
Micron MT4C1024 128KB RAM, zeptobars.org
CPSC 213 2020 ST1 © 2020 Jonatan Schroeder
5
▪Naming
▪unit of addressing is a byte (8 bits)
▪every byte of memory has a unique address
▪some machines have 32-bit memory addresses, some have 64
▪ For this course we will assume our machine has 32 bits, and all addresses are valid
▪Access
▪lots of things are too big to fit in a single byte
▪ unsigned numbers > 255, signed numbers < -128 or > 127, most instructions, etc. ▪CPU accesses memory in contiguous, power-of-two-size chunks of bytes ▪address of a chunk is address of its first byte
CPSC 213 2020 ST1 © 2020 Jonatan Schroeder 6
CPSC 213 2020 ST1 © 2020 Jonatan Schroeder 7
▪Sometimes we are interested in the integer value of chunk of bytes
▪base 10, decimal, is commonly used to represent this number (our “normal” number system)
▪we need to convert from binary to decimal to get this value ▪Sometimes we are more interested in bits themselves
▪memory addresses are big numbers that name power-of-two size things
▪we do not usually care what the base-10 value of an address is ▪we’d like a power-of-two sized way to name addresses
CPSC 213 2020 ST1 © 2020 Jonatan Schroeder 8
▪We might use base-2, binary
▪a small 256-byte memory has addresses 02 to 111111112 ▪may be represented as 0b11111111
▪but, as addresses get bigger, this is tedious
▪Once we used base-8, octal
▪64-KB memory addresses go up to 11111111111111112 = 1777778 ▪may be represented as 0177777
▪but, as addresses got bigger, this got tedious too
▪Now we use base-16, hexadecimal
▪4-GB memory addresses go up to 377777777778 = ffffffff16 ▪if you don’t have subscripts, ffffffff16 is written as 0xffffffff
CPSC 213 2020 ST1 © 2020 Jonatan Schroeder
9
hex
bin
0
0000
1
0001
2
0010
3
0011
4
0100
5
0101
6
0110
7
0111
8
1000
9
1001
A
1010
B
1011
C
1100
D
1101
E
1110
F
1111
01101010010101010000111010100011 ▪4 bits in a hex “digit”, a hexit (or “nibble”)
0110 1010 0101 0101 0000 1110 1010 0011 ▪Consider ONE hexit at a time
6a550ea3 0x6a550ea3
▪A byte (8 bits) is just 2 hexits (28 = 162): 0x6a550ea3 => 0x6a 0x55 0x0e
0xa3
CPSC 213 2020 ST1 © 2020 Jonatan Schroeder
10
▪Which of the following statements is true?
A. B. C. D.
The Java constants 16 and 0x10 are exactly the same integer The Java constants 16 and 0x10 are different integers Neither of the statements above is always true
I don’t know
CPSC 213 2020 WT2 © 2021 Jonatan Schroeder 11
▪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 complement
▪Remember that:
▪carry when result is 0x10 == 1610 or more ▪hexits a..f convert to their decimal value
CPSC 213 2020 ST1 © 2020 Jonatan Schroeder 12
▪Object A is at address 0x10d4, and object B at 0x1110. They are stored contiguously in memory (i.e., they are adjacent to each other). How big is A?
A. 16 bytes
B. 48 bytes
C. 60 bytes
D. 80 bytes
E. You can’t tell for sure from the information given
CPSC 213 2020 ST1 © 2020 Jonatan Schroeder 13
▪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? CPSC 213 2020 ST1 © 2020 Jonatan Schroeder
i i+1 i+2 i+3
…
i-1
i+4
…
14
▪We can start at the “big end”
▪The first byte is the most significant one ▪Used in old IBM servers, network connections
i i+1 i+2 i+3
i-1
0x12345678:
0x12
231 −224
0x34
223 −216
0x56
215 −28
0x78
27 −20
i+4
…
CPSC 213 2020 ST1 © 2020 Jonatan Schroeder
15
…
▪We can start at the “little end”
▪The first byte is the least significant one ▪Used in most Intel-based systems
i i+1 i+2 i+3
…
i-1
0x12345678:
0x12
231 −224
0x34
223 −216
0x56
215 −28
0x78
27 −20
i+4
…
CPSC 213 2020 ST1 © 2020 Jonatan Schroeder
16
▪The memory of some machines stores Big Endian integers. A. True
B. False
CPSC 213 2020 WT2 © 2021 Jonatan Schroeder 17
▪What is the Little-Endian 4-byte integer value at address 0x4? A. 0xc1406b37
B. 0x1c04b673
C. 0x73b6041c
D. 0x376b40c1 E. 0x739a8732
Address
Value
0x0:
0xfe
0x1:
0x32
0x2:
0x87
0x3:
0x9a
0x4:
0x73
0x5:
0xb6
0x6:
0x04
0x7:
0x1c
CPSC 213 2020 ST1 © 2020 Jonatan Schroeder 18
▪We could allow any number to address a 4-byte integer
▪However, requiring addresses to be aligned is better for hardware
CPSC 213 2020 ST1 © 2020 Jonatan Schroeder 19
▪What is an “aligned” address?
▪Address whose numeric value 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
CPSC 213 2020 ST1 © 2020 Jonatan Schroeder 20
▪CPU implementation encourages alignment
▪Memory is organized internally into chunks (blocks)
▪Every memory access requires accessing a whole block ▪ Details: see CPSC 313
▪CPU memory access looks like: ▪Read/write 𝑁 bytes starting at address 𝐴
▪This is translated by memory to:
▪Block 𝐵 contains addresses 𝑋. . (𝑋 + 𝑏𝑙𝑜𝑐𝑘𝑠𝑖𝑧𝑒 − 1)
▪𝑋 ≤ 𝐴 ≤ 𝑋 + 𝑏𝑙𝑜𝑐𝑘𝑠𝑖𝑧𝑒 − 1
▪Read/write 𝑁 bytes starting at 𝑂th byte of block 𝐵 (𝐴 = 𝑋 + 𝑂)
CPSC 213 2020 ST1 © 2020 Jonatan Schroeder 21
▪So:
▪Block 𝐵 contains addresses 𝑋. . (𝑋 + 𝑏𝑙𝑜𝑐𝑘𝑠𝑖𝑧𝑒 − 1)
▪𝑋 ≤ 𝐴 ≤ 𝑋 + 𝑏𝑙𝑜𝑐𝑘𝑠𝑖𝑧𝑒 − 1
▪Read/write 𝑁 bytes starting at 𝑂th byte of block 𝐵 (𝐴 = 𝑋 + 𝑂)
▪How is this simplified if: ▪𝑏𝑙𝑜𝑐𝑘𝑠𝑖𝑧𝑒 is power of 2
▪𝑋 and 𝑁 are powers of 2 ▪𝐴 is aligned to 𝑁?
CPSC 213 2020 ST1 © 2020 Jonatan Schroeder 22
▪Which of the following statements is (are) true?
A. B. C. D. E.
6 = 1102 is aligned for addressing a short (2 byte) integer
6 = 1102 is aligned for addressing a 4 byte integer
20 = 101002 is aligned for addressing a long (8 byte) integer
All of the above None of the above
CPSC 213 2020 ST1 © 2020 Jonatan Schroeder 23
▪Which of the following statements is (are) true?
A. The address 0x14 is aligned for addressing a 2-byte integer, but
not a 4-byte integer
B. The address 0x14 is aligned for addressing a 2-byte or a 4-byte integer, but not an 8-byte integer
C. The address 0x14 is aligned for addressing a 2-byte, 4-byte, or 8- byte integer
D. None of the above
E. If I say the answer is 42, maybe I’ll get the point anyway
CPSC 213 2020 WT2 © 2021 Jonatan Schroeder 24
▪Extending an integer: increasing the number of bytes used to store it
byte b = -6; // stored as 11111010
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?
CPSC 213 2020 ST1 © 2020 Jonatan Schroeder 25
▪Truncating an integer: reducing the number of bytes used to store it
int i = -6; // stored as 11111111111111111111111111111010 byte b = i; // stored as 11111111111111111111111111111010
▪What could go wrong?
▪What value would b get if i were 256? or 128?
▪Java warns you if you truncate implicitly ▪To avoid warning, cast explicitly:
byte b = (byte) i;
CPSC 213 2020 ST1 © 2020 Jonatan Schroeder 26
▪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, zero-extends, otherwise sign-extends ▪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
CPSC 213 2020 ST1 © 2020 Jonatan Schroeder 27
▪Shifting multiplies/divides by power of 2 ▪ “a<
▪Example: 22 in binary is 00010110
▪11 is 00001011 (22 shifted right once, Τ )
22 21 ▪44 is 00101100 (22 shifted left once, 22 × 21)
2
▪88 is 01011000 (22 shifted left twice, 22 × 22)
▪Works for negative numbers too, if using sign-extended shift
▪-22 is 11101010
▪-11 is 11110101 (-22 shifted right once, Τ )
−22
▪-44 is 11010100 (-22 shifted left once, −22 × 21)
21 ▪-88 is 10101000 (-22 shifted left twice, −22 × 22)
CPSC 213 2020 ST1 © 2020 Jonatan Schroeder 28
▪Review:
byte b = -6; // stored as 11111010
int i = b; // stored as 1111…1111 11111010
▪How can we get it to zero-extend instead of sign-extend?
▪Answer: using bit operations:
// 0xFF in bits is: 0000…000011111111
int i = b & 0xFF; // stored as 0000…000011111010
▪Note that the result is different: 250 instead of -6 ▪That’s because zero-extension is used for unsigned integers
CPSC 213 2020 ST1 © 2020 Jonatan Schroeder 29
▪What is the value of i after this Java statement executes? i = 0xff8b0000 & 0x00ff0000;
A. 0xffff0000
B. 0x0000008b
C. 0x008b0000
D. 0xff8b0000
E. None of the above
CPSC 213 2018 WT1 © 2018 Jonatan Schroeder 30
▪What is the value of i after this Java statement executes? i = 0x0000008b << 16; A. 0x008b B. 0x0000008b C. 0x008b0000 D. 0xff8b0000 E. None of the above CPSC 213 2018 WT1 © 2018 Jonatan Schroeder 31 ▪What is the value of i after this Java statement executes? i = 0x8b << 16; A. 0x8b B. 0x0000008b C. 0x008b0000 D. 0xff8b0000 E. None of the above CPSC 213 2018 WT1 © 2018 Jonatan Schroeder 32 ▪What is the value of i after this Java statement executes? i = ((byte) 0x8b) << 16; A. 0x8b B. 0x0000008b C. 0x008b0000 D. 0xff8b0000 E. None of the above CPSC 213 2018 WT1 © 2018 Jonatan Schroeder 33