PowerPoint Presentation
CSE 2421
Counting in Hex &
Integer Multiplication and Division
Counting in Hex
When examining hexadecimal numbers, as we often do with addresses, we will need to be able to do basic arithmetic operations, such as counting up (addition) or counting down (subtraction) when working in assembler.
The principles, of course, are exactly 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.
Counting in Binary and Hex – Example
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.
Some value
Store new value here
0x8000
0x????
Higher stack addresses
Lower stack addresses
System Stack
Counting in Binary and Hex
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
Counting in Binary and Hex
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
Base 10 Multiplication Remedial Review
a (multiplicand) * b (multiplier)
Consider a = 123, b = 123.
Binary (Base 2) Multiplication
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.
Hardware for integer multiplication (Simplest version)
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
Multiplication hardware
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
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.
Example
w=8, 0p1=4, op2=3
w(8) – 1 – op1(4) = 3
Example
w=8, 0p1=4, op2=3
w(8) – 1 – op1(4) = 3
Is op2 > w – 1 – op1? 3 > 3?
Example
w=8, 0p1=4, op2=3
w(8) – 1 – op1(4) = 3
Is op2 > w – 1 – op1? 3 > 3?
No overflow in this case.
32
Dividing by powers of 2
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
Alt+0247 (numeric key pad) to get a division symbol
Really is binary arithmetic although looks like decimal for the first two examples
Watch out for explanation of 3rd example
32
33
Unsigned Integer Division
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
34
Dividing by powers of 2
x = 8 = 1000
y = 2 = 0010 = 21
x >> 1 = 100 (x / y)
x = 9 = 1001
y = 2 = 0010 = 21
x >>1 = 100 (x / y)
34
35
Dividing by powers of 2
x = 12 = 1100
y = 4 = 0100 = 22
x >> 2 = 11
x = 15 = 1111
y = 4 = 0100 = 22
x >>2 = 11
35
36
Signed Integer Division
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
Note rounding effect
If truncate last column, does not always equal the decimal column
-82/2^k truncated (round to zero) == Dec (rd)
36
123
x123
==========================
369(this is 123 * 3)
246(this is 123 * 2 shifted left 1 place)
123(this is 123*1 shifted left 2 places)
============================================
15129
Sheet1
Carry In 1 1 0
A 4 5 6
B 2 8 9
Sum 7 4 5
Carry Out 0 1 1
Carry In 1 1 0 0
Operand A 0 1 1 0
Operand B 0 1 1 1
Sum 1 1 0 1
Carry Out 0 1 1 0
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
Sheet2
Sheet3
1011(this is 11 in decimal)
x1110(this is 14 in decimal)
===================
0000(this is 1011 x 0)
1011(this is 1011 x 1, shifted one position to the left)
1011(this is 1011 x 1, shifted two positions to the left)
+1011(this is 1011 x 1, shifted three positions to the left)
===========================
10011010(this is 154 in decimal)
Sheet1
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)
Sheet2
Sheet3
8÷21009÷210012÷41115÷411
10100010100110011001001111
1010100100
0001100111
0000100100
001011
kDecimal-82/2
k
010101110-82-82.000000
111010111-41-41.000000
211101011-21-20.500000
311110101-11-10.250000
411111010-6-5.125000
511111101-3-2.562500
Binary