# CS计算机代考程序代写 Java 2020 – Winter Term 2

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<**>b” is equivalent to 𝑎 Τ𝑏
▪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