Transcript Slide 1

Two’s and one’s complement arithmetic
CLOCK ARITHMETIC
12
11
1
2
10
3
9
8
4
7
5
6
12
11
1
2
10
3
9
8
4
7
5
6
2+3= ?
12
11
1
2
10
3
9
8
4
7
5
6
2+3= 5;
9+4=?
12
11
1
2
10
3
9
8
4
7
5
6
2+3= 5;
9+4=13=1;
7*3=?
12
11
1
2
10
3
9
8
4
7
5
6
2+3= 5;
9+4=13=1;
7*3=21=9
You can add and multiply in clock arithmetic; but you subtract multiples of 12 to get
the clock display (between 1 and 12) (or, better, between 0 and 11). In particular,
you can perform accurate, real arithmetic on a clock (without correction), as long as
you ensure your calculations don’t go beyond [0,11].
12=0
11
1
2
10
3
9
8
4
7
5
6
2+3= 5;
9+4=13=1;
7*3=21=9
A base-16 clock
0
15
1
14
2
13
3
12
4
11
5
10
6
9
3+4 = ?; 11+13 = ?
8
7
0
15
1
14
2
13
3
12
4
11
5
10
6
9
3+4 = 7; 11+13 = (24-16) = 8.
8
7
It’s easy for a computer to do base-16 clock arithmetic if the numbers are encoded in
binary.
0000
1111
0001
0
1110
15
1
0010
14
1101
2
0010
13
3
12
1100
4
0100
11
1011
5
10
0101
6
9
1010
8
7
0110
1001
1000
0111
Whenever a sum in base-16 clock arithmetic is 16 or greater, it acquires a fifth bit.
To subtract 16 in the binary form,
simply drop the fifth bit
(since 16 = 100002).
13
+ 5
18
||
2
or
11012
+ 01012
100102
||
0010 2
So to do base 16 arithmetic, use a binary 4-bit register and drop the “carry”
if it occurs in the 4th bit.
A base-15 clock
0
14
1
13
2
3
12
11
4
10
5
9
6
8
3+4 = ?; 11+13 = ?
7
0
14
1
13
2
3
12
11
4
10
5
9
6
8
3+4 = 7; 11+13 = 9
7
To implement base-15 arithmetic on a computer, again use the binary representation:
0000
0001
1110
0
14
1101
0010
1
13
1100
1011
2
12
3
11
4
0100
5
10
1010
0011
6
9
8
0101
7
1001
0110
1000
0111
Whenever a sum in base-15 clock arithmetic exceeds 15, it acquires a fifth bit.
Subtract 15
13
+ 5
18
||
3
or
1101
+ 0101
10010
||
0011
The easy way to subtract 15 in binary is to subtract 16 and add 1.
Subtract 16 by removing the fifth bit.
Then to add 1 you can imagine that the fifth bit is “carried around” to the
first bit.
1101
+ 0101
10010
+1
______
0011
So you can do base-15 clock arithmetic with standard bit-adders, linking the 4thbit carry to the first bit.
So it’s easy to use standard bit-adders to do base-2n clock arithmetic; simply drop
the “carry” in the final bit.
And it’s almost as easy to use standard adders to do base-[2n-1] clock arithmetic;
simply connect the “carry” in the final bit to the first bit.
Next we will show how to interpret clock arithmetic in these two systems as
signed arithmetic. We will not alter the computations or the hardware; we will
simply interpret the numbers differently.
Can you subtract on a standard clock? Are there negative numbers?
12
11
1
2
10
3
9
8
4
7
5
6
2-5=?
Can you subtract on a standard clock? Are there negative numbers?
12
11
1
2
10
5
3
9
8
4
7
5
6
2-5=9
(-1) is the solution to x + 1 = 0. So (-1) = 11. And (-2) = 10.
0
(-1)
11
1
(-2)
2
10
3
9
8
4
7
5
6
Of course this respects the rule, because (-1) + 12 = 11; (-2) + 12 = 10.
Therefore clock arithmetic replicates real arithmetic for numbers between
(-6) and +5, if we identify 11 with -1, 10 with -2, …, 6 with -6.
(0)
(-1)
11
0
(1)
1
(2)
(-2)
2
10
(-3)
3
9
8
(3)
4
(-4)
(4)
7
(-5)
5
6
(5)
(-6)
(-3) + 2 = -1 because 9 + 2 = 11 ; (-3) + 5 = 2 because 9 + 5 = 2 on the clock.
For example we can compute 3 – 5 = 3 +(-5) by adding the clock version of
(-5) to 3.
(0)
(-1)
11
1
(2)
(-2)
(-5)
10
(-3)
(1)
0
2
3
9
8
(+7)
4
(-4)
(4)
7
(-5)
5
6
(-6)
3 – 5 = 3 + 7 = 10 = -2 .
(5)
(3)
So the rules for signed clock arithmetic are:
1. Make sure your calculations don’t call for any numbers beyond [-6,5].
2. Identify -1 with 11, -2 with 10, -3 with 9, -4 with 8, -5 with 7, -6 with 6.
3. Perform the signed addition [like 3 – 2 = 3 + (-2)] by doing the normal addition
with clock arithmetic, using 0 through 11. (So if any answer lies outside [0,11],
“repair” it by adding or subtracting 12.)
4. Identify 11 with -1. 10 with -2, 9 with -3, 8 with -4. 7 with -5, and 6 with -6.
The hard parts, for computer implementation, are
(i) making it easy to look at a coded negative number and identify its positive
twin in steps 2 and 4.
(ii) repairing any answer that lies out of the range in step 3.
We have seen how the binary representation of the clock numbers makes (ii)
very easy if the clock has 2n or 2n-1 numbers. Now we will show how 2’s
complement and 1’s complement arithmetic, in the binary system, simplify (i).
Identify the negative numbers on the base-16 (=24) clock.
(0)
(-1)
15
(-2)
(1)
0
1
(2)
14
(-3)
2
13
(-4) 12
4
(-5) 11
5
10
(-6)
(3)
3
6
9
(-7)
8
(-8)
7
(7)
(6)
(4)
(5)
Now write the original clock numbers in binary form.
0000
(0)
1111
1110
(-1)
15
(-2)
0001
(1)
0
1
(2)
14
1101
(-3)
2
13
4
(-5) 11
1010
5
10
(-6)
(3)
3
1100 (-4) 12
1011
0010
(4)
(-7)
8
(-8)
1001
1000
7
0101
(6)
(7)
0111
0100
(5)
6
9
0010
0110
Recall our first objective: “(i) making it easy to identify negative numbers with their
positive twins…” It’s easy to identify the negative numbers: their leading digit is
“1”.
0000
(0)
1111
1110
(-1)
15
(-2)
0001
(1)
0
1
(2)
14
1101
(-3)
2
13
4
(-5) 11
1010
5
10
(-6)
(3)
3
1100 (-4) 12
1011
0010
(4)
(-7)
8
(-8)
1001
1000
7
0101
(6)
(7)
0111
0100
(5)
6
9
0010
0110
Recall our first objective: “(i) making it easy to identify negative numbers with their
positive twins…” Get the positive twin by subtracting the number from 16
(100002).
0000
(0)
10000-1111=0001
(-1)
15
(-2)
0001
(1)
0
1
(2)
14
(-3)
2
13
(-4) 12
10000-1100=0100
4
(-5) 11
5
10
(-6)
(3)
3
6
9
(-7)
10000-1001=0111
8
(-8)
7
(7)
0111
(6)
(4) 0100
(5)
Recall our first objective: “(i) making it easy to identify negative numbers with their
positive twins…” Get the positive twin by subtracting the number from 16
(100002).
0000
(0)
10000-1111=0001
10000-1110=0010
10000-1101=0011
(-1)
15
(-2)
0001
(1)
0
1
(2)
14
(-3)
2
13
(-6)
10000-1010=0110
(3)
3
(-4) 12
10000-1100=0100
(-5) 11
10000-1011=0101
0010
4
5
10
(4)
8
7
(-7)
(-8)
(7)
10000-1001=0111
0111
10000-1000=1000
0100
(5)
0101
6
9
0011
(6)
0110
Recall our first objective: “(i) making it easy to identify negative
numbers with their positive twins…”.
If the binary number starts with 0, interpret it as a positive
number or zero.
If the binary number starts with 1, interpret it as the negative
of [100002 minus the number]. This is called (the negative of)
the 2’s complement of the number.
0000
(0)
1111
1110
(-1)
15
(-2)
0001
(1)
0
1
(2)
14
1101
(-3)
2
13
4
(-5) 11
1010
5
10
(-6)
(3)
3
1100 (-4) 12
1011
0010
(4)
(-7)
8
(-8)
1001
1000
7
0101
(6)
(7)
0111
0100
(5)
6
9
0010
0110
CONCLUSION
The 2’s complement system
The 2’s complement system codes numbers with n bits.
n = 4 in our example.
Positive numbers from 0 to 2n-1-1 are written in standard binary notation, and are
identified by that fact that their leading bit is zero.
0 to 7 in our example.
Negative numbers from –2n-1 to -1 are coded as their “2’s complement’, which is 2n
minus the absolute value of the number, and are identified by the fact that their
leading bit is one.
-8 to -1 in our example.
Calculations are performed using ordinary arithmetic with the numbers binary
coded, using an n-bit register, and dropping any “carry” in the nth bit.
The user must avoid overflow, which occurs if any number larger than [2n-1-1] or
lower that -2n-1 is computed.
How about negative numbers on a base-15 clock?
0
14
1
13
2
3
12
11
4
10
5
9
6
8
4-7=?
7
How about negative numbers on a base-15 clock?
0
14
1
13
2
12
3
7
11
4
10
5
9
6
8
4-7=12
7
The negative numbers are as shown:
(0)
(-1)
14
(-2)
(1)
0
1
(2)
13
2
(-3) 12
3
(-4) 11
4
(-5)
5
10
9
6
8
(-6)
(-7)
7
(7)
(6)
(5)
(3)
(4)
Now write the original numbers in binary form. Note that 0 (which is equivalent to 15)
has two representations now, as 0000 and as 1111.
1110
1101 (-2)
1111
0000
(0)
(-1)
14
0001
(1)
0
0010
(2)
1
13
2
1100 (-3) 12
3
(-4) 11
4
1011
(-5)
5
10
1010
8
(-6)
1001
(-7)
1000
(6)
0110
0111
0100
0101
7
(7)
(4)
(5)
6
9
(3) 0011
Recall our first objective: “(i) making it easy to identify negative numbers with their
positive twins…” Again it’s easy to identify the negative numbers: their leading
digit is “1”. (Sometimes we call 1111 the “negative zero.”)
1110
1101 (-2)
1111
0000
(0)
(-1)
14
0001
(1)
0
0010
(2)
1
13
2
1100 (-3) 12
3
(-4) 11
4
1011
(-5)
5
10
1010
8
(-6)
1001
(-7)
1000
(6)
0110
0111
0100
0101
7
(7)
(4)
(5)
6
9
(3) 0011
Recall our first objective: “(i) making it easy to identify negative numbers with their
positive twins…” Get the positive twin by subtracting the number from 15, i.e.
(11112).
1111
0000
(0)
1111-1110=0001
0001
(1)
(-1)
0
14
1
(-2)
(2)
13
2
(-3)
1111-1011=0100
12
(-4) 11
(-5)
(3)
3
4
10
5
(5)
9
(-6)
8
(-7)
1111-1000=0111
7
6
(6)
(7)
0111
(4) 0100
Recall our first objective: “(i) making it easy to identify negative numbers with their
positive twins…” Get the positive twin by subtracting the number from 15, i.e. (11112).
This is too easy. Change every 1 to 0 and every 0 to 1.
1110
1101 (-2)
0000
(0)
(-1)
14
0001
(1)
0
0010
(2)
1
13
2
1100 (-3) 12
3
(-4) 11
4
1011
(-5)
5
10
1010
8
(-6)
1001
(-7)
1000
(6)
0110
0111
0100
0101
7
(7)
(4)
(5)
6
9
(3) 0011
Recall our first objective: “(i) making it easy to identify negative
numbers with their positive twins…”.
If the binary number starts with 0, interpret it as a positive
number or zero.
If the binary number starts with 1, interpret it as the negative
of the number obtained by changing each bit. This the (the
negative of) the 1’s complement of the number.
1110
1101 (-2)
1111
0000
(0)
(-1)
14
0001
(1)
0
0010
(2)
1
13
2
1100 (-3) 12
3
(-4) 11
4
1011
(-5)
5
10
1010
8
(-6)
1001
(-7)
1000
(6)
0110
0111
0100
0101
7
(7)
(4)
(5)
6
9
(3) 0011
CONCLUSION
The 1’s complement system
The 1’s complement system codes numbers with n bits.
n = 4 in our example
Positive numbers from 0 to (2n-1-1) are written in standard binary notation, and are
identified by that fact that their leading bit is zero.
0 to 7 in our example
Negative numbers from –(2n-1-1) to -1 are coded as their “1’s complement’, which
means every bit is changed from 0 to 1 or from 1 to 0; and are identified by the fact
that their leading bit is one.
-7 to -1 in our example
As a result, 0000 is identified with 1111, which is sometimes called “negative zero.”
Calculations are performed using ordinary arithmetic with the numbers binary
coded, using an n-bit register, except that any “carry” generated in the nth bit of a
sum is carried around and added to the first bit.
The user must avoid overflow, which occurs if any number larger than (2n-1-1) or
lower that –(2n-1-1) is computed.