Transcript Assembly Language Programming

Arithmetic for Computers
CPSC 252 Computer
Organization
Ellen Walker, Hiram College
Encoding Numbers
• Two symbols (1 vs. 0)
– Binary logic easiest to implement
electronically
• How to represent arbitrary numbers?
– Ascii Characters
– 4 bits per decimal digit (Binary Coded
Decimal)
– Raw binary (base 2 numbers)
ASCII vs. BCD vs. Binary
•
33 in ASCII
00110011 00110011 (8*log10 bits)
•
33 in Binary Coded Decimal
0011 0011
•
(4*log10 bits)
33 in Binary
100001
log2 bits
Bit Numbering Convention
• Bits numbered from right to left, starting
with 0
33 = 0 0 1 0 0 0 0 1
Bits: 7 6 5 4 3 2 1 0
• Bit 0 is Least Significant Bit (LSB)
• Bit 7 is Most Significant Bit (MSB)
Signed Numbers (Sign /
Magnitude)
• Sign + Magnitude
– One bit used for sign (convention 1 =
negative)
– N-1 bits for magnitude
• Difficulties
– 2 representations for 0
– Where does the sign go? (MSB vs. LSB)
– Complex addition algorithm
Two’s Complement
• MSB (sign bit) is the -2^(N-1) place and
all other bits are 2^x (0<=x<N-1)
• Advantages:
– No changes to addition algorithm
– Easy negation (flip the bits and add 1)
– Easy test for negative (MSB is 1)
Largest & Smallest Values
• N bits can represent 2^N combinations
– Unsigned: 0 to (2^N) - 1
– Sign/Magnitude -(2^N-1)+1 to (2^N-1)-1
– 2’s Complement -2^N-1 to (2^N-1)-1
• Arithmetic operations that result in
values outside this range cause
arithmetic overflow
Arithmetic Overflow
• Arithmetic overflow occurs when the
sign bit is incorrect after an operation
• Example (8 bit 2’s complement)
01111111
127
+ 00000011
3
-------------------10000010 -126
Unsigned Integers
• If negative values aren’t appropriate,
use all bits
• Values from 0 to (2^N)-1 (all positive)
• Example: addresses
Effect on Instruction sets
• Instructions for both signed and
unsigned values
– Loading / storing
– Comparisons
– Arithmetic / Logic operations
Sign Extension
• When copying a shorter signed number into a
longer register, don’t change the sign!
– 11110000 = 111111110000, not 000011110000
• To avoid this, replicate the sign bit all the way
to the MSB
• Sign bit replication never changes the value
of a number
Shortcuts for Decimal to
Binary
• Compute minimal bit pattern for
absolute value
– Repeated divide-by-two, saving
remainders
– MSB must be 0 (add one if needed)
• If negative value is desired, flip the bits
and add 1
• Sign-extend to required number of bits
Decimal-to-binary examples
• 1037 (16 bit)
• -38 (8 bit)
Loading Numbers into
Registers
• A complete register - lw
– No special cases, since all 32 bits specified
• A byte
– lb (load byte) sign-extends
– lbu (load byte unsigned) pads with 0’s
• A halfword (2 bytes)
– lh (load halfword) sign-extends
– Lhu (load halfword unsigned) pads with
0’s
Comparisons
• Set on less than (slt, slti)
– Treats registers as signed numbers
• Set on less than unsigned (sltu, sltui)
– Treats registers as unsigned numbers
• Example
– $s1 holds 00….001, $s2 holds 11..110
– Slt $t0, $s1, $s2 puts 0 in $t0
– Sltu $t0, $s1, $s2 puts 1 in $t0
Shortcut for 0<=x < y
• Bit patterns for negative numbers, when
treated as unsigned, are larger than all bit
patterns for positive numbers. (Why?)
• If (unsigned) x < (unsigned) y, and y is known
to be positive, we also know that x is positive.
• Use sltu to check both negative and too big in
one instruction.
Integer Addition & Subtraction
• Algorithm in base 2 is same as base 10
• Add up each column of numbers from
right to left
– A column consists of 2 numbers plus the
carry from the previous column (0 if first
column)
– If the sum is greater than 1, carry a 1 to the
next column, e.g. 1+1+1 = 3 (1, carry the 1)
One-Column Addition Table
In1
0
0
0
0
1
1
1
1
In2
0
0
1
1
0
0
1
1
C in
0
1
0
1
0
1
0
1
Out
0
1
1
0
1
0
0
1
C out
0
0
0
1
0
1
1
1
Addition example (8 bit 2’s
complement)
• Carry shown above in red
01100000
00110100
+ 00010010
-------------------01000110
52
18
70
Subtraction
• Use the usual subtraction algorithm with
borrows
• Negate the second operand, then add
– Advantage: reuse existing hardware
– Negation is easy in hardware
• Bit flip
• Increment
Overflow (Signed Numbers)
• Adding two positive numbers
– Overflow if sign bit becomes 1
• Adding two negative numbers
– Overflow if sign bit becomes 0
• Adding positive and negative number
– Overflow cannot occur (why?)
Signed Overflow Detection
Algorithm
• IF the sign bits of the operands are
equal,
• AND the sign bit of the result does not
equal the sign bits of the operands
• THEN overflow has occurred
Unsigned Integers
• Overflow could be detected by having a
separate sign bit in addition to the 32 bit
register
• However, overflow in memory
addresses is commonly ignored
– “Wrap” from highest to lowest location
Relevant Instructions
• Add, addi, sub, subi
– Detect overflow and cause an exception
when it occurs
• Addu, addiu, subu
– Never cause an overflow exception
Dealing with Overflow
• Exception code (like a procedure call)
• Special conditional branch
– Many architectures, not MIPS
– “Branch on overflow” instruction
• Write your own code
– Do an unsigned arithmetic operation
– Check signs of operands and result
– Use xor operation: 1 if different, 0 if equal (see p.
228)
Consequences of Fixed
Integer Representations
• Limited number of values (both positive and
negative)
• Moving from shorter to longer format requires
sign extension
• Unsigned representations allow twice as
many values (but no negatives)
• Arithmetic overflow must be detected
– Correct algorithm on valid inputs yields incorrect
result
Multiplication
• Multiplication result needs twice as
many bits
– E.g. 7*7 = 49 (7 is 3 bits, 49 is 6 bits)
• Multiplication is more complex than
addition/subtraction
– Develop algorithm, implement using
simpler hardware
Multiplication Algorithms
• Repeated addition
– Easy to implement in software
– Can only multiply positive numbers directly
– Time depends on magnitude of operands
• Shift-and add
– Efficient use of hardware
– Time depends only on width of operands
– No special case for negative numbers
Shift and Add Algorithm
• For each bit in multiplier
– If bit = 1, add multiplicand to result
– Shift multiplicand left by 1
Shift and Add example
10101
X 101
--------10101
000000
+ 1010100
-----------------1101001
21
5
(included for completeness)
105 (1+8+32+64)
Division
• Use the long division algorithm (shift
and subtract)
• Put 1 in the quotient whenever leading
bit is 1, else put 0 in the quotient
• When all bits from dividend have been
used, if difference is not 0, it is the
remainder.
Division Example
10101
101 | 1101001
101
0110
101
0101
101
0