Digital Logic�Lecture 3�� �Binary Arithmetic

​

By

Zyad Dwekat

The Hashemite University

Computer Engineering Department

The Hashemite University

2

Outline

• Introduction.
• Numbers range.
• Sign extension.
• Overflow detection.
• Unsigned numbers addition and subtraction.
• Signed numbers addition and subtraction.
• Examples.

The Hashemite University

3

Introduction

• Computers perform the arithmetic operations in Binary.
• Computers perform arithmetic on fixed-size numbers which is called finite-precision arithmetic that is the operands and the result are stored in a fixed size memory storage and cannot be exceeded.
• The rules for finite-precision arithmetic are different from the rules of ordinary arithmetic (which are performed by humans in decimal).
• The general design rule is to simplify operations as possible in order to get simpler and lower cost logic circuits implementation for these operations.

The Hashemite University

4

Numbers in Computers

• Two types of numbers are found in computers:
• Unsigned: the concept of +ve and –ve numbers does not exist. Simply can be considered to contain +ve numbers only where all bits within the number can be used to represent the magnitude of the number (no bits are reserved).
• Signed: the number contains a sign representation. So, you have +ve and –ve numbers. One bit (which is the MSB) is reserved for the sign. So, the magnitude of the number occupies (n – 1) bits (for an n bit number).
• Unsigned numbers have exactly one representation in Binary systems.
• Signed numbers have many different representation systems where we will deal with only 3 of them.
• Signed and unsigned concepts are applicable for all numbering systems (decimal, octal, hexa, binary, …).

​

The Hashemite University

5

Signed Binary Numbers

• In decimal system the sign is represented using – and + symbols.
• However, such symbols cannot be used by hardware where every thing must be binary (either 0 or 1).
• So, the MSB of a binary number is reserved for the sign (i.e. sign bit):
• 0 🡪 +ve number.
• 1 🡪 -ve number.

The Hashemite University

6

Signed Binary Numbers Representation

• Signed-magnitude system:
• the MSB represents the sign, the remaining bits represent the number value (the value is the same as in unsigned numbers).
• Negates the number by reversing its sign.
• Hard to be used for binary operations in computers.
• Signed-complement system:
• the MSB gives an indication about the sign but not reserved for it.
• Negates a number by taking its complement (either 1’s or 2’s complement).
• Taking the complement of the positive number includes the sign bit which becomes 1 (-ve) in all cases.
• Convenient to be used by computers (actually the 2’s complement is the most common).

The Hashemite University

7

Complements

• The complement of a number B is the number that when added to B you get either the quantity rⁿ or (rⁿ – 1) based on the complement type.
• Two types of complement systems:
• Diminished radix complement: or simply (r – 1)’s complement (r is the radix).
• Radix complements: or simply r’s complement.
• In binary they are called: 1’s and 2’s complement.
• In decimal: 9’s and 10’s complement.
• In octal: 6’s and 7’s complement.
• In hexa: 15’s and 16’s complement.
• We are mainly interested in binary and decimal complements (to see how arithmetic operations are performed by computers).

The Hashemite University

8

Diminished Radix Complement

• In this system we have: B + (-B) = (rⁿ - 1)
• So, in general for number N which contains n digits:

(r – 1)’s complement = (rⁿ - 1) – N

• Very Important Note: rⁿ is computed in decimal then before subtraction you convert it into the proper numbering system that you are working with. OR just put a 1 followed by n zeros.

The Hashemite University

9

Binary 1’s Complement – Simple Rule

• Simply invert each bit in the binary number: 1 🡪 0 and 0 🡪 1
• Examples:

​

The Hashemite University

10

Floating Point Diminished Radix Complement

• Remove the radix point temporarily and find the (r – 1)’s complement then put the floating point in its original relative location in the result (the same location found in the original number).

The Hashemite University

11

Floating Point Diminished Radix Complement -- Examples

The Hashemite University

12

Radix Complement

• In this system we have: B + (-B) = rⁿ
• So, for number N which contains n digits:

r’s complement = rⁿ – N

• So:

r’s complement = 1 + (r - 1)’s complement

• The rule of rⁿ calculations is the same as in the (r-1)’s complement.
• Special rule for 2’s complement in Binary:
• Start from the LSB and leave all 0’s without change in addition to the first 1 you encounter. After that invert all remaining bits (0 🡪 1 and 1 🡪 0).
• For floating point apply the same rule used by (r – 1)’s complement: Remove the radix point temporarily and find the r’s complement then put the floating point in its original relative location in the result.

The Hashemite University

13

Radix Complement -- Examples

The Hashemite University

14

Remember ...

• Negative of the negative is positive.
• So, applying complement twice for a number you return to the original number (none complemented one).

The Hashemite University

15

Number Ranges I

• Unsigned System:
• Has one zero
• Number range: 0 to 2ⁿ -1
• Signed-magnitude and the signed 1’s complement:
• Have two zeros (-ve and +ve zero).
• Symmetric values for both +ve and –ve directions (i.e. mirror).
• Number range: -(2^{n – 1} - 1) to +(2^{n – 1} - 1).
• Signed 2’s complement:
• Has one +ve zero (more natural).
• Asymmetric (there is an additional value in the negative direction).
• Number range: - 2^{n – 1} to +(2^{n – 1} - 1).

​

​

The Hashemite University

16

Number Ranges II

​

• Note that:

​

• The number of values that can be represented by an n bit number = 2ⁿ (same for signed and unsigned numbers)

The Hashemite University

17

Number Format and Arithmetic Operations

• In life we are working with:
• Integer numbers: no fractions.
• Real numbers: a floating point exists.
• We need special representation for floating point numbers since computers deals with fixed size numbers represented in binary.
• Many standards exist to represent real numbers in binary, e.g. NIST, IEEE 754 standard.
• Arithmetic operations:
• Addition.
• Subtraction.
• Multiplication.
• Division.
• In this lecture we will deal with addition and subtraction (only) for signed and unsigned Integer numbers and floating point numbers in ordinary representation (contain radix point as we write in daily life).

The Hashemite University

18

Arithmetic Operations -- Notes

• Big Picture:
1. Make sure that the two number you are adding os subtracting are of the same size (have the same number of bits).
• This is done by sign extension as shown in the next slide.
2. Perform the required operation (addition or subtraction).
3. Check if there is overflow or not (see next slides).
• If there is overflow, then the operation is incorrcet, no answer.
• If there is not overflow, then the operation is correct, take the answer.

The Hashemite University

19

Sign Extension Concept I

• If you are given the following two unsigned numbers to be added which they are not of equal number of bits what will you do?

11101 + 00111010

• Sol:
• Remember in the unsigned system there is no –ve numbers. So, to reserve the value of the number you must add zeros to the left of the number (since they have no value)
• So it becomes 🡪 00011101

The Hashemite University

20

Sign Extension Concept II

• If you are given the following two signed numbers (using the 2’s complement) to be added which they are not of equal number of bits what will you do?

11101 + 00111010

• Sol:
• 11101 is a –ve number since MSB = 1. you must extend the sign bit to reserve the sign of the number.
• So it becomes 🡪 11111101

The Hashemite University

21

Overflow

• Arithmetic operation may not obtain the correct answer in some cases. This happens when the result is out of range that the reserved bits can represent.
• For example, when 8-bit binary code is used to represent a number in the 2’s complement system, the range of numbers that can be represented is from -128 to +127. If the result of an operation lies outside this range, overflow occurs.
• Overflow occurs because of the finite precision arithmetic of the computer hardware.
• Computers checks for overflow and set a flag in case of over flow.
• The user can check this flag to know the current overflow status.

The Hashemite University

22

Overflow Detection

• Overflow cases:
• Unsigned numbers:
• Addition: an overflow occurs if C_out from the MSB is not equal to 0.
• Subtraction: as in signed numbers as shown below.
• For signed numbers three cases exist this depends on the used system to represent –ve numbers:
• Sign-magnitude system 🡪 will not be studied
• 1’s and 2’s complement system 🡪 C_in != C_out means there is an overflow (C_in is the carry into the MSB).
• This is checked in the 1’s complement before performing the end-around carry step.

The Hashemite University

23

Binary Addition and subtraction

• We will study them as follows:
• Unsigned Addition and subtraction: deal with unsigned number systems.
• Signed Addition and subtraction: deal with signed number systems both 1’s and 2’s complement systems.

​

The Hashemite University

24

Binary Addition – Basic

0

+ 0

0

0

+ 1

1

1

+ 0

1

1

+ 1

1 0

Carry Bit

(a)

(b)

(c)

(d)

1

+ 1

1

11

(e)

Carry Bit

Remember Counting Principles

The Hashemite University

25

Unsigned Binary Addition --Examples

(a)

(b)

(c)

(d)

(e)

All calculations are right, no overflow, (Cout = 0)!!

The Hashemite University

26

Unsigned Addition – Other Systems

• Pay attention to the used numbering system.
• Simply convert the number into decimal or binary (if you are working in octal or hexa) and perform addition then convert the result back to the original numbering system that you started from.

The Hashemite University

27

Unsigned Binary Subtraction I

• All subtraction operations can be converted into addition by taking complements (to reserve the simplicity rule):

A – B = A + (-B)

• Remember we are dealing with unsigned numbers (no –ve numbers).
• So, (-B) in the above example is the complement of B not the –ve quantity of B.
• Such general rule is applied for all numbering systems.

The Hashemite University

28

Unsigned Binary Subtraction II

• So, perform unsigned subtraction using complements:
• r’s complement unsigned subtraction (2’s complement in binary).
• (r – 1)’s complement unsigned subtraction (1’s complement in binary).
• Different rules are applied for each method.
• The basic method is the r’s complement unsigned subtraction.

The Hashemite University

29

r’s Complement Unsigned Subtraction

• To subtract M – N:
• Find the r’s complement of N and add it to M.
• If a carry out produced then it must be discarded which means that M >= N.
• If no carry out produced this means that M < N, in this case the result of the subtraction is – (N – M), i.e. –ve of the difference. So, find the r’s complement of the result and place a – sign in front of it.

The Hashemite University

30

Examples I

Ex. 1: Compute 25₁₀ – 25₁₀ using 2’s complement, n = 8.

​

00011001₂ = (25₁₀)

+ 11100111₂ = (-25₁₀)

---------------------------

100000000₂ = (0₁₀)

discard

The calculation is right, no overflow, (Cin = Cout)!!

The Hashemite University

31

Examples II

Ex: Compute 115₁₀ – 39₁₀ using 2’s complement, n = 8.

115₁₀ - 39₁₀ = 115₁₀ + (-39₁₀)

-39₁₀ = 11011001₂ (2’s)

​

01110011₂ = (115₁₀)

+ 11011001₂ = (-39₁₀)

---------------------------

101001100₂ = (76₁₀)

​

discard

The calculation is right, no overflow, (Cin = Cout)!!

The Hashemite University

32

Examples III

Ex. 3: Compute 0101₂ – 1100₂ using 2’s complement, n = 4.

– 1100₂ = 0100₂ (2’s)

​

0101₂

+ 0100₂

-------------

1001₂

The calculation is wrong !! Cin != Cout, Overflow

The Hashemite University

33

Examples IV

Ex. 4: Compute 0001₂ – 0110₂ using 2’s complement, n = 4.

– 0110₂ = 1010₂ (2’s)

​

0001₂

+ 1010₂

-------------

1011₂ => no carry out

The answer is the 2’s complement of 1011= - (0101)

The calculation is right, no overflow, (Cin = Cout)!!

The Hashemite University

34

(r – 1)’s Complement Unsigned Subtraction

• To subtract M – N:
• Find the (r – 1)’s complement of N and add it to M.
• If a carry out produced then it must be discarded (which means that M >= N) and then add 1 to the result. This method is called end-around carry.
• If no carry out produced this means that M < N, in this case the result of the subtraction is – (N – M), i.e. –ve of the difference. So, find the (r - 1)’s complement of the result and place a – sign in front of it.

​

The Hashemite University

35

Examples I

Ex. 1: Compute 25₁₀ – 25₁₀ using 1’s complement, n = 8.

​

00011001₂ = (25₁₀)

+ 11100110₂ = (-25₁₀)

---------------------------

11111111₂

Final answer = - (1’s of 11111111₂) = - 00000000₂

The calculation is right, no overflow, (Cin = Cout)!!

The Hashemite University

36

Examples II

Ex. 2: Compute 115₁₀ – 39₁₀ using 1’s complement, n = 8.

115₁₀ - 39₁₀ = 115₁₀ + (-39₁₀)

-39₁₀ = 11011000₂ (1’s)

01110011₂ = (115₁₀)

+ 11011000₂ = (-39₁₀)

---------------------------

101001011₂

+ 1₂

---------------------------

01001100₂ = (76₁₀)

​

discard

The calculation is right, no overflow, (Cin = Cout)!!

The Hashemite University

37

Examples III

Ex. 3: Compute 0101₂ – 1100₂ using 1’s complement, n = 4.

– 1100₂ = 0011₂ (1’s)

0101₂

+ 0011₂

-------------

1000₂ 🡪 No carry out

The calculation is wrong !! Cin != Cout, Overflow

The Hashemite University

38

Example IV

Ex. 4: Compute 11₂ – 10.11₂ using 2’s complement where n = 8.

– 00000010.11₂ = 11111101.01₂ (2’s)

00000011.00₂

+ 11111101.01₂

-------------

100000000.01₂

discard

The calculation is right, no overflow, (Cin = Cout)!!

The Hashemite University

39

Examples V

Ex. 5: Compute 0001₂ – 0110₂ using 1’s complement, n = 4.

– 0110₂ = 1001₂ (1’s)

​

0001₂

+ 1001₂

-------------

1010₂ => no carry out

The answer is the 1’s complement of 1011= - (0100)

The calculation is right, no overflow, (Cin = Cout)!!

The Hashemite University

40

Signed Binary Arithmetic

• Which system to use?
• We will use the complement signed system.
• Using signed complements we need one circuit to perform both addition and subtraction because subtraction can be done by addition.
• No sign checking of operands is required 🡪 simpler in hardware.
• Also, overflow detection is very easy using this system.
• 2’s complement is preferred over 1’s complement because no duplication of zero exist.

​

The Hashemite University

41

2’s Complement Signed Binary Addition

• Represent –ve numbers in 2’s complement (if not already in binary).
• Add numbers and if a carry out obtained discard it.
• If the result is –ve (i.e. the MSB is 1) then it is in the 2’s complement form.

The Hashemite University

42

1’s Complement Signed Binary Addition

• Represent –ve numbers in 1’s complement (if not already in binary).
• Add numbers and if a carry out obtained discard it and add 1 to the result (end-around carry method).
• If the result is –ve (i.e. the MSB is 1) then it is in the 1’s complement form.

The Hashemite University

43

Signed Binary Subtraction

• Convert the subtraction into addition by taking the complement of the second operand.
• Then, apply the same rules of addition for both types of complements.
• Note that arithmetic operations for both signed and unsigned numbers are the same but the difference lies in the interpretation of the results.

The Hashemite University

44

Example I

Find the following using 2’s complement (signed):

115 - 39 = 115 + (-39)

First: convert into binary

115₍₁₀₎ = 01110011₍₂₎ (2‘s)

-39₍₁₀₎ = 11011001₍₂₎ (2’s)

Second: perform subtraction using 2’s complement:

01110011 = (115)

+ 11011001 = (-39)

---------------------------

101001100 = (76)

discard

The calculation is right, no overflow, (Cin = Cout)!!

The Hashemite University

45

Example II

Find the following using 2’s complement (signed):

68 + 39

First: convert into binary:

68₍₁₀₎ = 01000100₍₂₎ (2‘s)

99₍₁₀₎ = 01100011₍₂₎ (2’s)

Second: add using 2’s complement:

01000100 = (68)

+ 01100011 = (99)

---------------------------

10100111 = (-89)

The calculation is wrong !! Cin != Cout

The actual answer (i.e. 167) exceeds the largest limit (i.e. 127) =>OVERFLOW

The Hashemite University

46

Example III

Find the following using 2’s complement (signed):

-78 - 52 = (-78) + (-52)

First: convert into binary:

-78₍₁₀₎ = 10110010₍₂₎ (2‘s)

-52₍₁₀₎ = 11001100₍₂₎ (2’s)

Second: subtract using 2’s complement :

10110010 = (-78)

+ 11001100 = (-52)

---------------------------

101111110 = (126)

The calculation is wrong !! Cin != Cout overflow

discard

The Hashemite University

47

Examples IV

Ex. : Compute 0001₂ – 0110₂ using 1’s complement, n = 4, signed.

– 0110₂ = 1001₂ (1’s)

​

0001₂

+ 1001₂

-------------

1010₂ => no carry out

The answer is 1011

The calculation is right, no overflow, (Cin = Cout)!!

The Hashemite University

48

Examples V

Ex. 5: Compute 0001₂ – 0110₂ using 2’s complement, n = 4, signed.

– 0110₂ = 1010₂ (2’s)

​

0001₂

+ 1010₂

-------------

1011₂ => no carry out

The answer is 1011

The calculation is right, no overflow, (Cin = Cout)!!

The Hashemite University

49

Additional Notes

• This lecture covers the following material from the textbook:
• Chapter 1: Sections 1.5 – 1.6