Arithmetic for Computers: Important Example Solved Problems

Example: 6

Draw half adder using NAND gates.

Solution: For half adder :

Example: 7

Give means to identify on whether or not an overflow has occurred in 2's complement addition or subtraction operations. Take one example for each possible situation and explain. Assume 4‒bit registers.

Solution:

Case 1: Both numbers positive

Result is – 6 ; it is wrong due to overflow.

Case 2: Both numbers negative

Result is +7 ; it is wrong due to overflow.

Binary Multiplication

Example: 1

 Recode the multiplier 1 0 1 1 0 0 for Booth's multiplication.

Solution :

Example: 2

Recode the multiplier 0 1 1 0 0 1 for Booth's multiplication.

Solution :

Example: 3

Multiply 0 1 1 1 0 (+14) and 1 1 0 1 1(‒5).

Solution :

Multiplication:

Note: Shaded portion indicates sign extensions

• The same algorithm also can be used for negative multiplier and negative multiplicand. This is illustrated in the following example.

Example: 4

Explain the following pair of signed 2's complement numbers.

Multiplicand: 1 1 0 0 1 1 (‒13)

Multiplier  : 1 0 1 1 0 0 (‒20)

Solution :

Multiplication :

Note: Shaded portion indicates sign extensions

Example: 5

 Using Booth's algorithm multiply the following:

Multiplicand+ 12

Multiplier = ‒5

Solution:

Multiplicand = + 12 (0 1 1 0 0)

Multiplier = ‒5 (1 1 0 1 1)

Multiplication :

Example: 6

Multiply (‒7) and (+ 3) using Booth's algorithm. Register size is 5 bits.

Solution:

Multiplicand = ‒7 (1 1 0 0 1)

Multiplier = + 3 (0 0 0 1 1)

Multiplication :

Example: 7

Using Booth's algorithm multiply the following:

Multiplicand = ‒13

Multiplier = + 11

Solution:

Multiplicand = ‒13 (1 0 0 1 1)

Multiplier = + 11 (0 1 0 1 1)

Multiplication :

Example: 8

 Using Booth's algorithm multiply the following :

Multiplicand= + 13 Multiplier = ‒5

Example: 9

 Using Booth's algorithm multiply

Multiplicand = ‒ 13 Multiplier = + 15.

Fast Multiplication

Example: 1

Find the bit‒pair code for multiplier.

1 1 0 1 0.

Solution: By referring table we can derive bit‒pair code as follows:

Example: 2

Multiply given signed 2's complement numbers using bit‒pair recoding

A = 1 1 0 1 0 1 multiplicand (‒11)

B = 0 1 1 0 1 1 multiplier (+27)

Solution:

 Let us find the bit‒pair code for multiplier.

Multiplication:

Example: 3

Give the Booth's recoding and bit‒pair recoding of the number.

1 0 0 0 1 1 1 1 0 1 0 0 0 1 0 1

Solution: Booth's recoding

Bit‒Pair recoding

Example: 4

Multiply the following pair of signed 2's complement numbers using bit‒pair recoding of the multipliers: A = 010111, B = 101100.

Solution :

A = 0 10 1 1 1         Multiplicand (+23)

B = 1 0 1 1 0 0         Multiplier (‒20)

Let us find the bit‒pair code for multiplier

Multiplication

2's complement of the multiplicand

2's complement of the multiplicand

(‒460)

Example: 5

Explain Booth's algorithm to multiply the following pair of signed two's complement numbers

A = 110011 multiplicand

B = 101100 multiplier

Also, implement the above using bit‒pair Recoding and explain how it achieves faster multiplication

Solution :

Implementation with bit‒pair recoding

Bit‒pair recoding for multiplier : ‒1 ‒1 0

Multiplication

The Booth's algorithm may need the summation at each step and number of steps required in Booth's algorithm are equal to length of multiplier in bits. The bit‒pair recoding halves the maximum number of summations. Hence it achieves faster multiplication.

Example: 6

Show the multiplication of (+13) and (‒6) using multiplier bit pair recoding technique.

Solution :

     + 13 = 0 1 1 0 1

     ‒ 6 = 1 0 1 0   2's complement of 6

Bit pair recoding of ‒ 6

Multiplication

 (+13) × (‒6) = (10110010)2 = (‒78)10

Example for Practice

Example: 7

Illustrate multiplication of signed 2's complement numbers 01101 and 11010 using bit‒pairing of the multipliers.

Example: 8

Multiply 0112 by 1102 using binary multiplication method.

Solution :

• For multiplication in binary numbers, it uses n shifts and adds to multiply n‒bit binary number.

• The combination logic circuit implemented to perform such multiplication is called combinational multiplier or array multiplier.

Binary Division

Example: 1

Perform the division of following numbers using restoring division algorithm.

Dividend = 1 0 1 0

Divisor = 0 0 1 1

Solution:

Fig. 2.5.2 shows steps involved in the above binary division.

Example: 2

 Divide the following unsigned numbers using restoring division method

Dividend = 1000, Divisior = 11.

Solution :

Example: 3

Perform the following division using restoring division algorithm :

Dividend = 1001

Divisor = 0101.

Solution :

Example: 4

Perform 1100+ 11 using restoring algorithm.

Solution:

Restoring Division: Q← Dividend (1100), B← Divisor (11).

2's Complement of divisor (B) = 11101.

Example: 5

Using restoring division algorithm solve the following:

Dividend = 17.

Divisor = 03

Solution :

Dividend = 17 = 17 = (10001)2 → Q

Divisor = 03 = 03 = (00011)2 → B

2's complement of B = (111101)2

• The division algorithm just discussed needs restoring register A after each unsuccessful subtraction. (Subtraction is said to be unsuccessful if the result is negative). Therefore it is referred to as restoring division algorithm.

Example: 6

Perform restoring division when divisor V = 3 and dividend D = 7. Also give the results for all possible combinations of signs of D and V.

Solution:

The restoring division algorithm assumes positive signs of D and V.

Remainder = (0001)2 = 1 and Quotient = (0010)2 = 2

• In the division operation, the magnitudes of quotient (Q) and remainder (R) are unaffected by the input signs. The signs of Q and R are easily derived from the signs of D and V using expression: D=Q × V + R

• The signs of Q and R for all possible combinations of signs of D and V are as FB follows:

D =7,      V=3    ⇒    Q=2,    R=1

D =7,      V= ‒3    ⇒    Q= ‒2,    R=1

D = ‒7,      V=3    ⇒    Q= ‒2,    R= ‒1

D = ‒7,      V= ‒3    ⇒    Q=2,    R= ‒1