Transcript Session 4

Ethics of Computing
MONT 113G, Spring 2012
Session 4
Binary Addition
1
Signed Magnitude
We want to represent both positive and negative integers. How?
Method 1 (Signed Magnitude): Use leftmost bit to indicate the
sign.
1 => negative number
0 => positive number
Example: Assume an 8 bit integer, represent +3 and -3
+3 = ?
+3 = 00000011
-3 = ?
-3 = 10000011
2
One's Complement
Method 2: One's Complement.
1st digit represents the sign (1 => negative)
If the number is negative, take the positive representation and
flip each bit (from 1 to 0 or from 0 to 1).
Example:
+3 = ?
+3 = 00000011
-3 = ?
-3 = 11111100
3
Two's Complement
Method 3: Two's complement
1st digit represents the sign (1 => negative)
If the number is negative, take the positive representation
and flip each bit (from 1 to 0 or from 0 to 1) and add 1.
Example:
+3 = ?
+3 = 00000011
-3 = ?
-3 = 11111101
4
Binary Addition
Addition: adding two positive numbers
Add 14 and 11:
14
+11
25
00001110
00001011
00011001
(Check result)
Subtraction: add a negative number to a positive number
Subtract 11 from 14.
14
- 11
3
00001110
- 00001011
00001110
+11110101
00000011
5
When the numbers are too big
What happens when we add 127 to 60, using 8 bit integers?
127
+60
187
01111111
00111100
10111011 = -69
What is the largest number we can represent with n bits?
1 bit for the sign.
Can represent 2n-1 -1 as the largest number.
With 8 bits, can represent 27 -1 = 127
6
Floating point representation
Floating point (real) numbers use 32 bits:
1 sign bit
7 bits for exponent
24 bit fraction
Recall scientific notation: 18,000 = 1.8 x 104
Example: 0 1000011 10101000 ... (rest zeros)
Sign is zero => positive
Exponent = + 3 (sign bit for exponent uses 1 for positive)
Fraction = .10101
23 x .10101 = 101.01 = 1 x 4 + 0 x 2 + 1 x 1 + 0 x .5 + 1 x .25
= 5.25
7
Recall Digital Gates
Other useful gates:
s1 V s2
OR Gate
NOR Gate
(s1 V s2)
XOR (Exclusive OR) Gate
AND Gate
(s1 L s2)
(s1 L s2)
NAND Gate
Inverter
s1
8
Building a Half-Adder
Design a circuit that, given 2 input digits will give the sum
and carry digits produced by adding the two inputs.
a
+b
cs
1
+1
10
1
+0
01
0
+1
01
0
+0
00
Truth Table
a b c s
9
The Half Adder Circuit
c=aLb
s = (a L b) V ( a L b)
10
Building a Full Adder
For the full adder, we must add three digits: The two from the
numbers we are adding and the carry digit.
a
b
+c
ed
1
1
+1
11
1
1
+0
10
1
0
+1
10
1
0
+0
01
0
1
+1
10
0
1
+0
01
0
0
+1
01
0
0
+0
00
a b c e d
Truth Table
11
Half of the full adder
a
b
c
out
12
Universal Building Blocks
One can build any logical circuit with the following gates:
2 input AND gate
2 input OR gate
Inverter
In fact, one can build any logical circuit with just 1 type of gate:
2 input NAND
13
Everything from NAND
NOT
a
true
z= a
AND
a
b
true
OR
a
true
b
true
z=aLb
z=aV b
14