Transcript 10 11 10 11 10 00 00 01 0 0 0 1 1 0 0 1 1 1 1 1 1 0

Computer Arithmetic
and the Arithmetic Unit
Lesson 2
- Ioan Despi
Digital Number Systems
• Digital number systems have a base or radix b
• Using positional notation, an m-digit base b number is
written
x = xm-1 xm-2 ... x1 x0
0  xi  b-1, 0  i < m
• The value of this unsigned integer is
m-1
value( x) =  x i b i
i=0
Range of Unsigned m Digit Base b
Numbers
• The largest number has all of its digits equal to b-1, the largest
possible base b digit
• Its value can be calculated in closed form
m-1
m-1
xmax =  ( b-1 ) b i = ( b-1)   b i = b m - 1
i=0
i=0
• An important summation—geometric series
m-1
m - 1
b
 bi = b - 1
i=0
Number Systems
• base 10 (decimal)
10 digits
0, 1, 2, 3, 4, 5, 6, 7, 8, 9
positional notation
1011ten = 1 x 103 + 0 x 102 + 1 x 101 + 1 x 100
• base 2 (binary)
2 digits
0,1
1011two = 1 x 23 + 0 x 22 + 1 x 21 + 1 x 20
1011two = 11ten
Number Systems
• base 8 (octal)
8 digits
0, 1, 2, 3, 4, 5, 6, 7
1001eight = 1 x 83 + 0 x 82 + 1 x 81 + 1 x 80
1001eight = 521ten
• base 16 (hexadecimal)
16 digits
0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F
1001sixteen = 1 x 163 + 0 x 162 + 1 x 161 + 1 x 160
1001sixteen = 4113ten
Number Systems: 2
•
•
•
•
The digital logic of computers: simple, reliable circuits (AND, OR and NOT
gates) that “lock” one of two states (On / Off, True / False, 0 / 1)
To represent numbers, a single binary digit (bit) can represent 2 possible
numbers (0 or 1).
We can add more bits to the number giving the additional bits a place value, just
as we do for decimal numbers (base 10).
Each additional bit doubles the number of possible combinations:
Number of bits
Possible
combinations
Range
2
4
0 .. 3
3
8
0 .. 7
4
16
0.. 15
8
256
0 .. 255
To convert a binary number to decimal, one just
adds up the place values of the 1-bits, as follows:
Bit position
Binary
number
7 6 5 4 3 2 1 0
The number
has 8 bits
1 1 0 1 1 1 0 1
I numbered
starting with 0
on the right-->
1
4
8
16
64
the place value
of each bit is 2
to the power of
the bit number
EX:
128
-------
You can try with 10100111
221
2 to the 7th =
128
A story:
Seven computer scientists went for a walk. After a while they
counted themselves: 0, 1, 2, 3, 4, 5, 6. One must be missing!
So they spent the rest of the day looking, but never figured out
where the 7th one could have gone.
This is known as an “off by one” error.
It is all too common.
To convert from decimal to binary:
divide by 2 repeatedly until 0 is reached
then the remainders, reading up, are the binary number
221 /2 = 110
r=1
110 / 2 = 55
r=0
55 / 2 = 27
r=1
27 / 2 = 13
r=1
13 / 2 = 6
r=1
6/2=3
r=0
3/2=1
r=1
1/2=0
r=1
Answer: 11011101
Radix Conversion: General Matters
• Converting from one number system to another involves
computation
• We call the base in which calculation is done c and the
other base b
• Calculation is based on the division algorithm
— For integers a and b, there exist integers q and r such
that a = qb + r, with 0  r  b-1
• Notation:
q = a/b
r = a mod b
Digit Symbol Correspondence
Between Bases
• Each base has b (or c) different symbols to represent the digits
• If b < c, there is a table of b + 1 entries giving base c symbols for
each base b symbol and b
• If the same symbol is used for the first b base c digits as for the
base b digits, the table is implicit
• If c < b, there is a table of b + 1 entries giving a base c number for
each base b symbol and b
• For base b digits  c, the base c numbers have more than one digit
Base 12: 0 1 2 3
Base 3:
4
5
6
7
8
9
A
B
10
0 1 2 10 11 12 20 21 22 100 101 102 110
Convert Base b Integer to
Calculator’s Base, c
1) Start with base b
x = xm-1 xm-2 ... x1 x0
2) Set x = 0 in base c
3) Left to right, get next symbol xi
4) Lookup base c number Di for symbol xi
5) Calculate in base c:
x = xb + Di
6) If there are more digits, repeat from step 3
• Example: convert 3AF16 to base 10
x=0
x = 16x + 3 = 3
x = 163 + 10(= A) = 58
x1658 + 15(= F) = 943
Convert Calculator’s Base Integer to
Base b
1) Let x be the base c integer
2) Initialize i = 0 and v = x & get digits right to left
3) Set Di = v mod b & v = v/b. Lookup Di to get xi
4) i = i + 1; If v  0, repeat from step 3
• Example: convert 356710 to base 12
3587  12 = 298 (rem = 11)  x0 = B
298  12 = 24 (rem = 10)  x1 = A
24  12 = 2 (rem = 0)  x2 = 0
2  12 = 0 (rem = 2)  x3 = 2
Thus 358710 = 20AB12
Negative Numbers
• need a representation for negative numbers
• use two’s complement
• binary number negated as follows
starting from rightmost bit and working left, copy up to and
including the first 1-bit; thereafter, write 1-bits for 0-bits and 0-bits
for 1-bits.
• example in 16-bit word
42
-42
0000 0000 0010 1010
1111 1111 1101 0110
Complement Number Systems
• Complement number systems use unsigned numbers to
represent both positive and negative numbers
• Recall that the range of an m digit base b unsigned number is
0  x  bm-1
• The first half of the range is used for positive, and the second
half for negative, numbers
• Positive numbers are simply represented by the unsigned
number corresponding to their absolute value
Complement Operations
for m-Digit Base b Numbers
• Radix complement of m-digit base b number x
xc = (bm - x) mod bm
• Diminished radix complement of x
x c = bm - 1 - x
• The complement of a number in the range 0xbm-1 is in
the same range
• The mod bm in the radix complement definition makes
this true for x = 0; it has no effect for any other value of x
• Specifically, the radix complement of 0 is 0
Complement Representations of
Negative Numbers
Radix Complement
Number
Representation
Diminished Radix Complement
Number
Representation
0
0
0
0 or bm-1
0<x<bm/2
x
0<x<bm/2
x
-bm/2x<0
|x|c = bm - |x|
-bm/2<x<0
|x|c = bm - 1 - |x|
• For even b, radix complement system represents one more
negative than positive value
• While diminished radix complement system has 2 zeros but
represents same number of positive & negative values
Base 2 Complement Representations
8 Bit 2’s Complement
Number
Representation
8 Bit 1’s Complement
Number
Representation
0
0
0
0 or 255
0<x<128
x
0<x<128
x
256 - |x|
-127x<0
255 - |x|
-128x<0
2 7  128
28  256
• In 1’s complement, 255 = 111111112 is often called -0
• In 2’s complement, -128 = 100000002 is a legal value, but trying
to negate it gives overflow
Digitwise Computation of the
Diminished Radix Complement
• Using the geometric series formula, the b-1’s complement of x
can be written
m-1
m-1
xc = b m -1 -x =  ( b-1 )  b i -  xi b i
i=0
i=0
m-1
=  ( b-1 -xi)  b i
i=0
• If 0xib-1, then 0(b-1-xi)b-1, so last formula is
just an m-digit base b number with each digit
obtained from the corresponding digit of x
Conversion Between Related Bases
by Digit Grouping
• Let base b = ck; for example b = c2
• Then base b number x1x0 is base c number y3y2y1y0,
where x1 base b = y3y2 base c and x0 base b = y1y0 base c
• Examples: 1021304 = 10 21 304 = 49C16
49C16 = 0100 1001 11002
1021304 = 01 00 10 01 11 002
0100100111002 = 010 010 011 1002 = 22348
Addition and Subtraction
• addition
bits are added and carry propagated leftwards
0000 0111 7ten
+ 0000 0110 6ten
= 0000 1101 13ten
• subtraction
use negation and addition i.e. x - y = x + (-y)
0000 0111 7ten
- 1111 1010 - 6ten
(2’s complement)
= (1) 0000 0001
1ten
Addition and Subtraction
• Addition (and subtraction) of binary numbers is similar to
ordinary addition.
• If the sum won’t fit in one bit, you need to carry one to the next
place on the left. The rules are:
0+0=0
1+0=1
0+1=1
1 + 1 = 0 and a carry
1+ 1 + 1 (from a previous carry) = 1 and a carry
Examples:
(the second illustrates a “ripple effect”)
0001 100
<-- carries -->
1111110
10 10 11 00
01 11 11 11
+00 00 11 11
00 00 00 10
-------------------------------------------
------------------------------------------
10 11 10 11
10 00 00 01
Long binary numbers get hard for humans to read:
1100 1010 1110 1100 1011 0101 1100
1000 1111 1010 0111 0110 0001 0010 0011 0100 0110 0101, etc…
and it takes a long time to convert them into decimal ===>
we need a more readable representation: Bases 8, 16
Carry and Overflow
• need to take account of restricted word size
• carry : when unsigned numbers are added, a carry occurs when a
carry is propagated from the leftmost bit
1100 0000
+ 0100 0000
= (1) 0000 0000
192ten
64ten
0ten
(256)
• overflow : when signed numbers are added, a overflow occurs when
the carry into the sign bit differs from the carry out of it
0100 0000 64ten
+ 0100 0000 64ten
1000 0000 -128ten
Multiplication
• algorithm operates on two unsigned n-bit numbers, a and b
• initialisation
load a into multiplier register A
load b into multiplier register B
clear register P
• repeat n times
1. if rightmost bit of A is 1-bit, then add B to P
2. shift P and A right, with rightmost bit of P shifting into leftmost bit of A
• product is in P and A
Multiplication
Example a =5, b = 3
P: 0000
A: 0101
B: 0011
Iteration 1
P: 0001  A: 1010
B: 0011
Iteration 2
P: 0000  A: 1101
B: 0011
Iteration 3
P: 0001 
B: 0011
Iteration 4
P: 0000 
B: 0011
A: 1110
A: 1111
product in PA : 0000 1111
answer = 15
Division
• algorithm operates on two unsigned n-bit numbers, a and b
• initialisation
load a into divider register A, load b into divider register B
clear register P
• repeat n times
1. shift P and A left, with leftmost bit of A shifting into rightmost bit of P
2. subtract B from P
3. if result of subtraction is negative, set rightmost bit of A to 0-bit, otherwise
set to 1-bit and add B to P restoring its value
•
quotient in A, remainder in P
Division
example, a = 14, b = 3
P: 0000
B: 0011
Iteration 1
P: 0001 
B: 0011
Iteration 2
P: 0000 
B: 0011
A: 1110
A: 1100
A: 1001
Iteration 3
P: 0001 
B: 0011
A: 0010
Iteration 4
P: 0010 
B: 0011
A: 0100
quotient in A = 4
remainder in P = 2