Transcript SN7400 Quad 2-input Positive NAND

Addition of two binary numbers
1410
+2510
0 1 10 0 0
= 011102
= 110012
1 0 01 1 1
= 32 + 7 = 39
Addition
x y CarryIn Sum CarryOut
000
0
0
This is a “truth table” or
001
1
0
“complete enumeration” of
010
1
0
the addition of three binary
011
0
1
numbers
100
1
0
101
0
1
110
0
1
111
1
1
Check your work
Carry
Sum
111101
101101
45
+011101
+ 29
1001010
= 74
Fixed-Length Registers
• All practical digital devices have fixed-length registers
• This means that numbers in a computer are
represented by a fixed number of bits
– The earliest microprocessors were 4-bit devices
– Intel 8080 and the 6502 (Apple II) chips were 8-bit
– Intel 8088 (IBM PC) and Motorola 68000 (Mac)
are 16-bit devices
– Pentium chips and PowerPC chips are 32-bit
Range of a number
Overflow during addition
• A fixed-length register can only hold a Range of
numbers
• For a 4-bit device, the range of positive integers is
0 - 15
• For an 8-bit device the range of positive integers is
0 - 255
• When adding positive integers, Overflow occurs
when the sum falls outside the range of the register
Negative Numbers and On/Off Devices
• Binary Systems are made with devices that take on
exactly two states. These will be related to “1” and
“0”.
1
• The only states are “1” and “0”. There is no “-”
state!
• Therefore, to represent negative numbers, we adopt
the convention that the leftmost bit is the sign bit. “0”
indicates a positive number, while a “1” indicates a
negative number
Sign/Magnitude Representation
• The leftmost bit indicates the sign of the number.
The remaining bits give the magnitude of the number
(much like our decimal representation)
• In an 8-bit register
-3 = 10000011 = 1/ (sign bit) 0000011
• Sign/Magnitude representation is great for having the
ability for a human to read and understand what
number is represented
• Sign/Magnitude is lousy for math
+3 0000 0011
+
-3 1000 0011
=
1000 0110 = ? = - 6
Sign/Magnitude
Unless a problem requests a sign/magnitude interpretation,
it will be counted wrong!
2’s Complement
• 2’s complement representation is tied in with fixedlength registers, and utilize the solution to x + 1 = 0,
x=?
• In a 4-bit register,
–
• In an 8-bit register
–
1111 + 1 = ?
1111 + 1 = 0000
11111111 + 1 = ?
11111111 + 1 = 00000000
• The leftmost bit is the sign bit
“0” is positive, “1” is negative
• The magnitude of a negative number is not simply
given by reading the remaining bits
Procedure to create 2’s complement
Step 0: Write the number to fill the register (including leading zeroes)
Step 1: Complement each bit (0  1, 1  0)
Step 2: Add 1
In an 8-bit register, what is the two’s complement representation of - 48
?
+ 48 = 32 + 16 = 110000
but 8 bits, so + 48 = 00110000 {(sign bit) 0 (magnitude) 0110000}
+ 48 = 00110000
Step 1(complement bits): 00110000  11001111
Step 2(add 1):
11001111 + 1 = 11010000
Therefore, -48 = 11010000
Check the Answer
+48 = 00110000
+
=
-48 = 11010000
1) 00000000
Properties of 2’s Complement
2’s Complement has the properties of the minus sign
A + (-A) = 0
A + 2’s{A} = 0
- (- A) = A
2’s{ 2’s{A}} = A
A - B = A + (-B)
A - B = A + 2’s{B}
What Negative Number?
What is the decimal representation of
1001000?
1001000 = - ( - 1001000)
= - ( 1001000 + 1)
= - ( 0110111 + 1)
= - ( 0111000)
= - (32 + 16 + 8) = - 5610
Subtraction Example
Complete the addition below and convert both addends
and the sum to decimal to verify the result.
1001100
+ 0011101
= 1101001
1001100 = -(-1001100)
= -(1001100 + 1)
= -(0110011 + 1) = 0110100
= - (32 + 16 + 4) = - 52
0011101 = 16 + 13 = 29
1101001 = -(-1101001)
= -(1101001 + 1)
= -(0010110 + 1) = -(0010111)
= -(16 + 7)
= -23
Overflow, Signed Integers
• As has been shown, when numbers are treated as
signed integers, a “carry” of 1 from the addition of the
most significant bits DOES NOT indicate an overflow,
3
00011
+ (-3)
+11101
= 0
= 00000, with a carry of “1”
• For signed integers, overflow occurs when:
The addition of two positive numbers results in a
negative number, or
The addition of two negative numbers results in a
positive number
Overflow Examples
• In a 6-bit register
+ 17 =
010001
+ 16 =
+010000
=100001
100001 = - (011110 + 1) = - 011111 = -31
• In an 8-bit register
- 100 = - (0110 0100) = 1001 1011 +1 = 1001 1100
- 50 = - (0011 0010) = 1100 1101 +1 = 1100 1110
= 0110 1010
0110 1010 = 6A16=6*16 + 10 = +106
Overflow Summary
• For positive integers, overflow occurs when the carry
from addition of the leftmost bits is a “1”
• For signed integers, overflow occurs when either
The addition of two negative numbers gives a
positive number, or
The addition of two positive numbers gives a
negative number.