Transcript Binary arithmetic

CSE 111
Binary Arithmetic
Thanks to Dr. Schindler
Binary Addition
Addition Table
+
0
1
0
1
0
1
1
0
Carry
1
Using the above table, proceed as with base
ten.
Binary Addition
Example
Consider 1410 + 910 using binary addition
1
1110
+1001
10111
Sum = 101112 = 2310
Subtraction with 2’s Complement
Procedure (M-N)
Express minuend, M, and subtrahend, N, with
same number of integer bits
Add minuend, M, to 2’s complement of
subtrahend, N.
If an end carry occurs, discard it.
Indicates positive result
If not, the result is a negative value represented in
r’s complement notation.
Subtraction with 2’s Complement
Example #1
Consider 8110 - 4510 using 2's complement and 8
bits
10100012 - 001011012
2's complement of 4510 = 110100112
001010001 + 11010011 = 100100100
End carry occurs
Discard end carry
Difference = 001001002 = 3610
Subtraction with 2’s Complement
Example #2
Consider 5310 - 6010 using 2's complement and 8
bits
001101012 - 001111002
2's complement of 6010 = 110001002
00110101 + 11000100 = 11111001
No end carry
Result (111110012) is in 2's complement notation
Difference = 111110012 = -710
Overflow
An overflow occurs when the result of an
arithmetic operation falls outside the available
range that can be stored.
Overflow
Detection of overflow for addition of signed
numbers
Carries into & out of MSB (sign bit) differ
Two positive numbers added & negative result is
obtained
Two negative numbers added & a positive result is
obtained
Note that overflow cannot occur if two
numbers of differing signs are added
Number Ranges
Unsigned Numbers
0  2n-1
Example
8 Bit
 0255
16 Bit
 0 65,535
32 Bit
 04,294,967,295
64 Bit
 0 18,446,744,073,709,599,999
Number Ranges
Signed Numbers in Two’s Complement
Notation
-2n-1  2n-1-1
Example
8 Bit
 -128127
16 Bit
 32,76832,767
32 Bit
 -2,147,483,6482,147,483,647
64 Bit
 -9,223,372,036,854,780,000 9,223,372,036,854,779,999
Overcoming Overflow
If overflow occurs, how can we overcome it?
Additional bits are required
Overcoming Overflow
The Problem
Adding more bits is fine for an unsigned number,
but how about a signed number?
Example - Unsigned
Represent the unsigned number 38 as an 8-bit number
 00100110
Extend it to 16-bits
 0000000000100110
Example - Signed
Represent the signed number 38 as an 8-bit number
 11011010
Extend it to 16-bits and put 0’s in the new bit positions
 0000000011011010
 The problem is that this is not -38, it is +218
To preserve the sign and magnitude, the sign must be
replicated in the new positions
 1111111111011010
References
J. Glenn Brookshear, Computer Science - An
Overview, 11th edition, Addison-Wesley as an
imprint of Pearson, 2012
Daniel Hillis, The Pattern on the Stone, Basic
Books (Perseus Books Group), 1998
M. Morris Mano and Charles R. Kime, Logic
and Computer Design Fundamentals, Prentice
Hall, Inc., 2000
Victor P. Nelson, H. Troy Nagle, Bill D.
Carroll, and J. David Irwin, Digital Logic
Circuit Analysis and Design, Prentice Hall,
Inc., 1995
Donald D. Givone, Digital Principles and
Design, McGraw-Hill, 2003