Transcript Wakerly Section 2.4

Wakerly Section 2.4 and further
Addition and Subtraction of
Nondecimal Numbers
Addition and Subtraction
• Use same technique as decimal
• Except that the addition and subtraction
tables are different
• Already seen addition table
– Truth table for Sum and Cout function
Subtraction table
bin
0
0
0
0
1
1
1
1
x
0
0
1
1
0
0
1
1
y
0
1
0
1
0
1
0
1
bout
0
1
0
0
1
1
0
1
d
0
1
1
0
1
0
0
1
Examples
• 191+141 (Let’s first convert these to binary
as an exercise.)
• 210-109
Addition and Subtraction of
Octal and Hexadecimal Numbers
• Not really too different
• But the addition and subtraction tables must
be developed.
Section 2.5: Rep. of Negative
Numbers
• More accurately: representation of signed
numbers
– Signed-magnitude representation
– Radix-complement representation
• 2’s-complement representation
– Diminished radix-complement representation
– Ones’ complement representation
– Excess representations
Signed-magnitude representation
• Also called, “sign-and-magnitude representation”
• A number consists of a magnitude and a symbol
representing the sign
• Usually 0 means positive, 1 negative
– Sign bit
– Usually the entire number is represented with 1 sign bit
to the left, followed by a number of magnitude bits
Machine arithmetic with signedmagnitude representation
• Takes several steps to add a pair of numbers
– Examine signs of the addends
– If same, add magnitudes and give the result the same
sign as the operands
– If different, must…
• Compare magnitude of the two operands
• Subtract smaller number from larger
• Give the result the sign of the larger operand
• For this reason the signed-mag rep is not as
popular as one might think because of its
“naturalness”
Complement number systems
• Negates a number by taking its complement
instead of negating the sign
• Exact meaning of taking its complement is defined
in various ways – will see
• Not natural for humans, but better for machine
arithmetic
• Will describe 2 complement number systems
– Radix complement – very popular in real computers
– Diminished radix-complement – not very useful, may
skip or not spend much time on it
Radix-complement number
representation
• Must first decide how many bits to represent the
number – say n.
• Complement of a number = rn – number
• Example: 4-bit decimal:
– Original number = 3524
– 10’s complement = 10000-3524 = 6476
• 0 and positive numbers: 0000-4999
• Negative numbers: 5000-9999, where 9999 is
‘minus 1.’
Two’s-complement
representation
• Just radix-complement when radix = 2
• Used a lot in computers and other digital
arithmetic circuits
• 0 and positive numbers: leftmost bit = 0
• Negative numbers: leftmost bit = 1
• To find a number’s complement – just flip
all the bits and add 1
• See graphical view – Fig. 2.3, p. 40.
Two’s-Comp Addition and
Subtraction Rules
• Starting from 1000 (-8) on up, each successive 2’s
comp number all the way to 0111 (+7) can be obtained
by adding 1 to the previous one, ignoring any carries
beyond the 4th bit position
• Since addition is just an extension of ordinary
counting, 2’s comp numbers can be added by ordinary
binary addition!
• No different cases based on operands’ signs!
• Overflow possible
– Occurs if result is out of range
– To detect – happens if operands are the same sign but sum is
a different sign of that of the operands
Binary multiplication
• Grammar school method for decimal: add a list of
shifted multiplicands computed according to the
digits of the multiplier
• Same method can be used in binary
• For two unsigned operands, the only possible
values of the multiplier digits are 0 and 1
– Thus it’s trivial to form the shifted multiplicands
Binary multiplication in binary
on a machine
• More convenient to add each shifted multiplicand
as it is created to a partial product
• Will do an example.
• In general when we multiply an n-bit number by an
m-bit number, the result requires at most n+m bits
to express
• The shift-and-add algorithm requires m partial
products and additions to obtain result, but the 1st
addition is trivial (adding to 0)
Binary code for decimal numbers
•
•
•
•
Any encoding needs at least 4 bits/decimal digit
BCD (8421), a weighted code
Packed BCD
2421 code
– Self-complementing: the code for the 9s’ comp of any
digit may be obtained by complementing the individual
bits of the digit’s code word
• Excess 3
– Not a weighted code, but is also self-complementing
– Since code follows standard binary counting sequence,
standard binary counters can easily be made to count in
excess-3
Biquinary code
• Uses more than 4 bits
• First 2 bits indicate whether the number is in the
range 0-4 or 5-0
– One-hot
• Last 5 bits indicate which of the five numbers in the
selected range is represented
– Also one-hot
• Advantage: error-detection property. If any 1 bit in a
code word is accidentally changed to the opposite
value, the resulting code word doesn’t represent a
decimal digit at all – flagged as error.