CS计算机代考程序代写 compiler assembler algorithm Microsoft PowerPoint – 25_Int_Mult_Div

Microsoft PowerPoint – 25_Int_Mult_Div

O
SU

C
SE

2
42

1

J.E.Jones

Required Reading: Computer Systems: A Programmer’s Perspective, 3rd Edition

• Chapter 4, Sections 4.2 through 4.2.2
• Chapter 2, Sections 2.3 through 2.3.8
• Chapter 8, Section 8.2 through 8.2.4

O
SU

C
SE

2
42

1

J. E. Jones

• When examining hexadecimal numbers, as we often do with
addresses, we will need to be able to do basic arithmetic
operations, such as addition or subtraction when working in
assembler.

• The principles, of course, are the same as in decimal, but the
values of the digits are different (0-F in hex instead of 0-9 in
decimal).

• Let’s look at an example.

O
SU

C
SE

2
42

1

J. E. Jones

• Suppose the address of the top of the stack at the beginning of
some function is 0x8000.

• Suppose that an 8-byte value is pushed onto the stack after the
processor starts executing the function’s code.

• When the value is pushed onto the stack in that function, the
address stored in the stack pointer will decrease by 8 bytes.
Then, the value to be pushed will be written to that address.

• Recall that the stack grows downward in RAM (the addresses
decrease as we push more and more values onto the stack).

• Therefore, to get the address where the value will be pushed
onto the stack, we need to compute 0x8000 – 0x08.

O
SU

C
SE

2
42

1

J. E. Jones

Some value

Store new value here

0x8000

0x????

Higher stack addresses

Lower stack addresses

O
SU

C
SE

2
42

1

J. E. Jones

•If we were subtracting in decimal, it’s easy, right???

•Reduce the least significant digit by 8; there must be a “borrow” from the next
most significant digit, so we must reduce the value of the remaining digits by
1.

•Thus, the result is 7992

Borrow 7 9 9 10
Operand A 8 0 0 0
Operand B 0 0 0 8

Difference 7 9 9 2

O
SU

C
SE

2
42

1

J. E. Jones

•How do we subtract 8 from 8000 hex?

•Reduce the least significant digit by 8; there must be a “borrow” from the next
most significant digit, exactly like we would in a decimal subtract, except the
digits we use must represent hexadecimal values.

•Note Borrow in LSD (Least Significant Digit) is still 10, it’s just a
hexadecimal value 10 (16 decimal) and other columns are F (not 9 as in
decimal).

•Thus, the result is 7FF8, and this is the address at which the first value pushed
onto the stack will be stored (more on how the stack pointer changes later).

Borrow 0x7 0xF 0xF 0x10
Operand A 8 0 0 0
Operand B 0 0 0 8

Difference 7 F F 8

O
SU

C
SE

2
42

1

J. E. Jones

Some value

Store new value here

0x8000

0x7FF8

Higher stack addresses

Lower stack addresses

Note new value is stored in addresses 0x7FF8 to 0x7fff

O
SU

C
SE

2
42

1

J. E. Jones

a (multiplicand) * b (multiplier)

Consider a = 123, b = 123.

1 2 3
x 1 2 3

==========================
3 6 9 (this is 123 * 3)

2 4 6 (this is 123 * 2 shifted left 1 place)
1 2 3 (this is 123*1 shifted left 2 places)

============================================
1 5 1 2 9

O
SU

C
SE

2
42

1

J. E. Jones

Now consider:

a (multiplicand) * b (multiplier) where a = 1011 (11 decimal), b = 1110 (14 decimal)

This is the same process that we use for decimal multiplication!

One could say that binary multiplication is actually easier because each row is either just a
“shifted copy” of the multiplicand or it’s 0.

1 0 1 1 (this is 11 in decimal)
x 1 1 1 0 (this is 14 in decimal)

===================
0 0 0 0 (this is 1011 x 0)

1 0 1 1 (this is 1011 x 1, shifted one position to the left)
1 0 1 1 (this is 1011 x 1, shifted two positions to the left)

+ 1 0 1 1 (this is 1011 x 1, shifted three positions to the left)
===========================

1 0 0 1 1 0 1 0 (this is 154 in decimal)

O
SU

C
SE

2
42

1

J. E. Jones

Now consider:

a (multiplicand) * b (multiplier) where a = 1011 (11 decimal), b = 1110 (14 decimal)

This is the same process that we use for decimal multiplication!

One could say that binary multiplication is simpler because each row is either just a
“shifted copy” of the multiplicand or it’s 0.

1 0 1 1 (this is 11 in decimal)
x 1 1 1 0 (this is 14 in decimal)

===================
0 0 0 0 (this is 1011 x 0)

1 0 1 1 (this is 1011 x 1, shifted one position to the left)
1 0 1 1 (this is 1011 x 1, shifted two positions to the left)

+ 1 0 1 1 (this is 1011 x 1, shifted three positions to the left)
===========================

1 0 0 1 1 0 1 0 (this is 154 in decimal)

In our brain, we can hold
and/or add etc. more than
2 numbers at a time. So
adding these columns of
numbers isn’t a hard thing.

Machines can’t do that.
Recall that hardware gates
have only 3 inputs and 2
Output (sum & carry).

O
SU

C
SE

2
42

1

J. E. Jones

•Suppose we want the CPU to multiply two operands:
a (multiplicand) * b (multiplier)

•Typically, in the simplest version of multiplication hardware, 4 additional
registers are used:

-Multiplicand register (contains a copy of the multiplicand)
-Multiplier register (contains a copy of the multiplier)
-Shifted multiplicand register
-Result register

O
SU

C
SE

2
42

1

J. E. Jones

Multiplicand register

Multiplier register

Shifted multiplicand register

Result register

Registers are places on the CPU where data is stored, typically 8 bytes in size.

O
SU

C
SE

2
42

1

J. E. Jones

•For n bit multiplication, we can denote the bits in the multiplier as b0 (least
significant bit) to bn-1 (most significant bit)

•The hardware initializes the result register to 0

•Then, the hardware does the following (pseudo-code):

for (j = 0; j w – 1 – op1n , overflow due to shifting will occur
So, if op2n> 1 in our example, overflow occurs.

•Again, overflow may also occur due to addition, but the result
above describes cases where overflow will definitely occur due to
shifting.

O
SU

C
SE

2
42

1

J. E. Jones

 If w=8, op1n=4, op2n=3

 w(8) – 1 – op1n(4) = 3

O
SU

C
SE

2
42

1

J. E. Jones

 If w=8, 0p1n=4, op2n=3

 w(8) – 1 – op1n(4) = 3

 Is op2n > w – 1 – op1n? 3 > 3?

O
SU

C
SE

2
42

1

J. E. Jones

 If w=8, 0p1n=4, op2n=3

 w(8) – 1 – op1n(4) = 3

 Is op2n > w – 1 – op1n? 3 > 3?

 No overflow in this case.

O
SU

C
SE

2
42

1

J. E. Jones

•Even slower than integer multiplication
•Dividing by powers of 2  right shifting

-There are 2 types of right shifting:
-Logical – unsigned: fill with 0’s
-Arithmetic – two’s complement: fill with

copy of msb
•Integer division always truncates

-C float-to-integer casts round towards zero.
-Division by right shifting rounds down.
-These rounding errors generally accumulate

O
SU

C
SE

2
42

1

J. E. Jones

•Dividing by 2k
•Logical right shift by k (x>>k)
•Then rounding down (toward zero)
•Remember that logical shift will shift in zeroes to
fill the most significant bits when the original bit
pattern is shifted right

O
SU

C
SE

2
42

1

J. E. Jones

8÷2 1 0 0 9÷2 1 0 0 12÷4 1 1 15÷4 1 1
10 1 0 0 0 10 1 0 0 1 100 1 1 0 0 100 1 1 1 1

1 0 1 0 1 0 0 1 0 0
0 0 0 1 1 0 0 1 1 1
0 0 0 0 1 0 0 1 0 0
0 0 1 0 1 1

x = 8 = 1000
y = 2 = 0010 = 21
x >> 1  = 0100  (x / y)

x = 9 = 1001
y = 2 = 0010 = 21
x >>1 = 0100  (x / y)

O
SU

C
SE

2
42

1

J. E. Jones

8÷2 1 0 0 9÷2 1 0 0 12÷4 1 1 15÷4 1 1
10 1 0 0 0 10 1 0 0 1 100 1 1 0 0 100 1 1 1 1

1 0 1 0 1 0 0 1 0 0
0 0 0 1 1 0 0 1 1 1
0 0 0 0 1 0 0 1 0 0
0 0 1 0 1 1

x = 8 = 1000
y = 2 = 0010 = 21
x >> 1  = 100  (x / y)

x = 9 = 1001
y = 2 = 0010 = 21
x >>1 = 100  (x / y)

x = 12 = 1100
y = 4 = 0100 = 22
x >> 2  = 0011

x = 15 = 1111
y = 4 = 0100 = 22
x >>2 = 0011

O
SU

C
SE

2
42

1

J. E. Jones

•Two’s complement
•Sign extend for arithmetic shift (fill with copy of msb)
•Rounds down (away from zero for negative results)
•-7/2 will yield -4 rather than -3
•x = -82 y = 2k
k Decimal ‐82/2k

0 1 0 1 0 1 1 1 0 ‐82 ‐82.000000
1 1 1 0 1 0 1 1 1 ‐41 ‐41.000000
2 1 1 1 0 1 0 1 1 ‐21 ‐20.500000
3 1 1 1 1 0 1 0 1 ‐11 ‐10.250000
4 1 1 1 1 1 0 1 0 ‐6 ‐5.125000
5 1 1 1 1 1 1 0 1 ‐3 ‐2.562500

Binary

Note rounding effect