Data Representation

And
Arithmetic Algorithms
Binary Arithmetic

 Operations performed on Binary Numbers

Binary
Arithmetic

Binary Binary Binary Binary

Addition Subtraction Multiplication Division
Binary Arithmetic

 Binary Addition
 The rules for binary addition are

Augend Addend Sum Carry Result

0 0 0 0 0
0 1 1 0 1
1 0 1 0 1
1 1 0 1 10

 E.g Add the binary numbers

 0101 and 1001
 0101 and 1111
Binary Arithmetic
▪ If no. of 1s to be added in a column are
 Binary Addition even, then the sum bit is 0.
 E.g Add the binary numbers
▪ If no. of 1s to be added in a column are
01101010 + 00001000 + 10000001 + 11111111 odd, then the sum bit is 1.

1
1 111 11 1
01101010
00001000
+
10000001
1 11111111
1 1 1 11 0 01 0
Binary Arithmetic

 Binary Subtraction
 The rules for binary subtraction are

Minuend Subtrahend Difference Borrow

0 0 0 0 1011 Minuend
−
0 1 1 1 0110 Subtrahend
1 0 1 0 1 Borrow
-------------
-------------
1 1 0 0 01 0 1 Difference

 E.g Subtract the binary numbers

 1011 and 0110
Binary Arithmetic

 Binary Multiplication
 Binary multiplication is similar to decimal multiplication
 Each partial product is either 0 (multiplication by 0) or exactly same as the multiplicand (multiplication by 1).
 Final product is the addition of all the partial products.
 E.g. Multiply 1010 and 1101
Binary Arithmetic

 Binary Division
 Binary division is obtained using same procedure as decimal division
 Type equation here.
1 101 Quotient
 E.g. Divide 1110101 by 1001
Divisor 1001 1110101 Dividend
1001

01011
1001
0 0 1 00
0000
01001
1001
0000
Signed Binary Numbers

 Sign Magnitude Representation

 An additional bit is used as the sign bit in a binary number
 A 0 is used to represent a positive number and 1 is used to represent a negative number.
 E.g.
 An 8-bit signed number 01000100 represents positive number with magnitude 68
 Similarly, 8-bit signed number 11000100 represents negative number with magnitude 68
One’s Complement Representation

 One’s Complement of a Binary Number

 Each 1 is replaced by 0 and each 0 is replaced by 1 in a binary number
 Resulting number is called as One’s complement of first number

01011 10100
 Both the number are complement of each other.
 If one of the number is positive, then the other number will be negative with same magnitude and vice versa

0 1 0 1 1 = 11 1 0 1 0 0 = -11
Signed Binary Numbers

 Two’s Complement Representation

 Add 1 to the one’s complement of a binary number to get Two’s complement of the given number.

Binary number: 01011

One’s Complement: 1 0 1 0 0
Add one + 1
-----------------
Two’s Complement: 1 0 1 0 1
Subtraction using 2’s Complement

 Step1: Find 2’s Complement of the subtrahend

 Step2: Add it to minuend

 Step3: if the final carry is 1, it is dropped and result is positive.

 Step4: if there is no carry, take 2’s complement of the sum to get the result and it is negative.

 E.g Subtract 10100.01 – 11011.10

2’s complement of 11011.10 is 00100.01

Minuend Subtrahend Minuend 10100.10

Result of Addition 11000.11

As no carry over the result of subtraction is negative.
2’s Complement of result is 00111.01
Hence, the result is – 𝟎𝟎𝟏𝟏𝟏. 𝟎𝟏
BCD Addition

 BCD is a numerical code which has several rules for addition.

 Addition is done BCD digit by BCD digit i.e. 4 bits at a time

 Binary addition of BCD numbers may result into invalid BCD codes i.e. numbers greater than 9

 If resulting value is greater than 9, add 6 to it

 This will offset the BCD code and generate the carry

 E.g. add 184 and 576

BCD Addition

 E.g. add 184 and 576

1 1
0001 1000 0100
+
0101 0111 0110

0111 10000 1010

0110 0110

0111 10110 10000

BCD Addition

 E.g. Perform addition of 2806 + 1897 in BCD

BCD Subtraction Using 9’s Complement

 The 9’s complement of a decimal number is obtained by subtracting each digit from 9.
 E. g. 9’s complement of 345 is 999-345 = 654

 Step 1: Find 9’s complement of the subtrahend.

 Step 2: Add it to the minuend.

 Step 3: If invalid BCD then add 0110 to it.

 Step 4: If there is End Around Carry, then result is positive and add carry to get the result.

 Step 5: If there is no End Around Carry, then take 9’s complement of the sum to get the result and
it is negative.
BCD Subtraction Using 9’s Complement

 E.g. Perform 78 – 33 in BCD using 9’s Complement

 9’s complement of 33 is 99-33 = 66

1
0 1 1 1 1 0 0 0
+
0 1 1 0 0 1 1 0

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

1 0 1 0 01 0 1 0 0
𝟏
1

0 1 0 0 0 1 0 1
BCD Subtraction Using 9’s Complement

 E.g. Perform 27 – 33 in BCD using 9’s Complement

BCD Subtraction Using 10’s Complement

 The 10’s complement is obtained by adding 1 to the 9’s complement of a number.

 E. g. 10’s complement of 345 is 999-345 = 654 +1 = 655

 Step 1: Find 10’s complement of the subtrahend.

 Step 2: Add it to the minuend.

 Step 3: If invalid BCD then add 0110 to it.

 Step 4: If there is End Around Carry, then result is positive and discard the carry and get the
result.
 Step 5: If there is no End Around Carry, then take 10’s complement of the sum to get the result
and it is negative.
BCD Subtraction Using 10’s Complement

 E.g. Perform 18 – 42 in BCD using 10’s Complement

 10’s complement of 42 is 99 – 42 = 57 +1 = 58
BCD Subtraction Using 10’s Complement

 E.g. Perform 78 – 33 in BCD using 10’s Complement

 10’s complement of 33 is 99-33 = 66 +1 = 67

1
0 1 1 1 1 0 0 0
+
0 1 1 0 0 1 1 1

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

1 0 1 0 0 1 0 1 0 1
𝟏
Hexadecimal Arithmetic

 Hexadecimal Addition
 Add the two hexadecimal digits by working with their decimal equivalent
 If the decimal sum is less than 16, write down the hex equivalent.
 If the decimal sum is more than 15, then subtract 16 from the sum and write down the hex result and
carry 1 to the next digit.
 E.g. Add 5𝐴𝐶 and 𝐵13

0101 1010 1100

+ 1011 0001 0011
𝟏 0000 1011 1111
1 0 𝐵 𝐹
Hexadecimal Arithmetic

 Hexadecimal Subtraction
 Take 2’s complement of the subtrahend
 Add minuend to the 2’s complement of the subtrahend
 If the sum is less than 16, write down the hex equivalent.
 If the decimal sum is more than 15, then subtract 16 from the sum and write down the hex result and
carry 1 to the next digit.
 If the MSB bit is 1, then the result is negative and it is in 2’s complement form.
 E.g. Subtract 5𝐴𝐶 and 𝐵13
0101 1010 1100
+ 0100 1110 1101
1010 1001 1001 0101 0110 0111
5 6 7
The answer is −567
Multiplication

 Multiplication is complex operation as compared to addition and subtraction.

 Multiplication of Unsigned Binary Integers

 E.g. 11 × 13
1011 𝑀𝑢𝑙𝑡𝑖𝑝𝑙𝑖𝑐𝑎𝑛𝑑 (11)
×1101 𝑀𝑢𝑙𝑡𝑖𝑝𝑙𝑖𝑒𝑟 (13)
1011
0000
1011 𝑃𝑎𝑟𝑡𝑖𝑎𝑙 𝑃𝑟𝑜𝑑𝑢𝑐𝑡𝑠
1011

1 0 00 1 1 1 1 𝑃𝑟𝑜𝑑𝑢𝑐𝑡 (143)
Multiplication

 Multiplication of Signed Binary Integers

 Case 1: Negative multiplicand and positive multiplier
 Take 2’s complement of negative multiplicand and append 1 as a sign bit in MSB
 E.g. −11 will be represented as
 2’s complement of 11 is 0101
 Append sign bit in MSB → 10101
 Extend the sign bit value of the multiplicand to the left side of partial product
 Perform addition of all partial products
 Discard carry generated after 2𝑛 bit result (𝑛 is no. of bits in multiplicand and multiplier)
 Take 2’s complement of the result and the result is negative number.
Multiplication

 Multiplication of Signed Binary Integers

 Case 1: Negative multiplicand and positive multiplier

10101 𝑀𝑢𝑙𝑡𝑖𝑝𝑙𝑖𝑐𝑎𝑛𝑑 −11 (2′ 𝑠 𝑐𝑜𝑚𝑝𝑙𝑒𝑚𝑒𝑛𝑡 𝑜𝑓 − 11) 1 1 1 1 1 1 0 1 0 1

×01101 𝑀𝑢𝑙𝑡𝑖𝑝𝑙𝑖𝑒𝑟 (13)
0 0 0 0 0 0 0 0 0
11111 10101 1 1 1 1 0 1 0 1
0000 00000
𝑃𝑎𝑟𝑡𝑖𝑎𝑙 𝑃𝑟𝑜𝑑𝑢𝑐𝑡𝑠 1 1 1 0 1 0 1
11110101
1 11 0 1 0 1 0 0 0 0 0 0
00 00 0 0 1 1 1
1101110001 𝑅𝑒𝑠𝑢𝑙𝑡 1 1 1 1 1 1 1 1 1
0010001110 1′ 𝑠 𝐶𝑜𝑚𝑝𝑙𝑒𝑚𝑒𝑛𝑡 1 0 1 1 0 1 1 1 0 0 0 1
+ 1

0010001111 2′ 𝑠 𝑐𝑜𝑚𝑝𝑙𝑒𝑚𝑒𝑛𝑡 𝑖. 𝑒. 𝑃𝑟𝑜𝑑𝑢𝑐𝑡 (−143)

Multiplication

 Multiplication of Signed Binary Integers

 Case 2: Positive multiplicand and Negative multiplier
 Straightforward multiplication does not work
 E.g. 12 × −3
 2’s complement of 4-bit decimal number −3 is 1101

01100 10011100
×11101 01100011
+ 1
01100
00000 01100100
01100
01100 0 1 1 0 0 1 0 0 → 100
01100 Wrong answer
10011100
Booths Multiplication Algorithm

 Negative multiplier cannot be used directly in the normal method.

 One of the Solutions

 Convert both multiplier and multiplicand to positive numbers and perform the multiplication.
 Take 2’s complement of the result if and only if the sign of the two original numbers differed.

 Booths Algorithm
Booths Multiplication Algorithm

 Step 1: Initialize the registers Q = Multiplier, M = Multiplicand, A = 0, 𝑄−1 = 0 and n = count (no.
of bits used to represent multiplicand and multiplier)
 Step 2: Set 𝑄0 = 𝐿𝑆𝐵 𝑜𝑓 𝑀𝑢𝑙𝑡𝑖𝑝𝑙𝑖𝑒𝑟

 Step 3: The control logic scans the 𝑄0 and 𝑄−1 bits and decides one of the following actions
 Step 3.1: If 𝑄0 , 𝑄−1 = 10 then A = A – M (addition of A with 2’s complement of M) go to Step 3.4
 Step 3.2: If 𝑄0 , 𝑄−1 = 01 then A = A + M go to Step 3.4
 Step 3.3: If 𝑄0 , 𝑄−1 = 00 𝑂𝑅 𝑄0 , 𝑄−1 = 11 them go to step 3.4
 Step 3.4: Perform Arithmetic right shift and decrease the count.

 If count >0, go to step 2 else stop.

 Start

𝐴 ← 0, 𝑄−1 ← 0,
𝑀 ← 𝑀𝑢𝑙𝑡𝑖𝑝𝑙𝑖𝑐𝑎𝑛𝑑,
𝑄 ← 𝑀𝑢𝑙𝑡𝑖𝑝𝑙𝑖𝑒𝑟,
𝑛 ← 𝐶𝑜𝑢𝑛𝑡

= 𝟏𝟎 = 𝟎𝟏
𝑄0 , 𝑄−1
= 𝟎𝟎
𝐴←𝐴−𝑀 = 𝟏𝟏 𝐴←𝐴+𝑀
Arithmetic right shift
𝐴, Q, 𝑄−1
𝑐𝑜𝑢𝑛𝑡 = 𝑐𝑜𝑢𝑛𝑡 − 1

𝑵𝒐
𝑐𝑜𝑢𝑛𝑡 = 0?

𝒀𝒆𝒔
Fig. Representation of the Booth's Algorithm End
Booths Multiplication Algorithm
 Example 1: Multiply −5 = 1011 and 2 = 0010

𝑪𝒐𝒖𝒏𝒕 𝑨 𝑸 𝑸−𝟏 𝑴 Operation

𝑛=4 0000 0010 0 1011 Initial Values
𝑛=3 0000 0001 0 Arithmetic Right shift
0101 0001 0 𝐴 ←𝐴−𝑀
𝑛=2 0010 1000 1 Arithmetic Right shift
1101 1000 1 𝐴 ←𝐴+𝑀
𝑛=1 1110 1100 0 Arithmetic Right shift
𝑛=0 1111 0110 0 Arithmetic Right shift

Result
11110110
As MSB is 1, the result is negative and is in 2’s complement form. 00001001
+ 1
0 0 0 0 1 0 1 0 = (−𝟏𝟎)𝟏𝟎
 Booths Multiplication Algorithm
 Example 2: Multiply 14 = 01110 and −5 = 11011

𝑪𝒐𝒖𝒏𝒕 𝑨 𝑸 𝑸−𝟏 𝑴 Operation

𝑛=5 00000 11011 0 01110 Initial Values
10010 11011 0 𝐴 ←𝐴−𝑀
𝑛=4 11001 01101 1 Arithmetic Right shift
𝑛=3 11100 10110 1 Arithmetic Right shift
01010 10110 1 𝐴 ←𝐴+𝑀
𝑛=2 00101 01011 0 Arithmetic Right shift
10111 01011 0 𝐴 ←𝐴−𝑀
𝑛=1 11011 10101 1 Arithmetic Right shift
𝑛=0 11101 11010 1 Arithmetic Right shift
0001000101
Result
+ 1
As MSB is 1, the result is negative and is in 2’s complement form.
0 0 0 1 0 0 0 1 1 0 = (−𝟕𝟎)𝟏𝟎
Booths Multiplication Algorithm
 Example 3: Multiply −12 = 10100 and −7 = (11001) 2’s complement of 10100 = 01100
𝑪𝒐𝒖𝒏𝒕 𝑨 𝑸 𝑸−𝟏 𝑴 Operation
𝑛=5 0 0 0 0 0 1 1 0 0 1 0 1 0 1 0 0 Initial Values
𝐴←𝐴−𝑀
Booths Multiplication Algorithm
 Example 3: Multiply −12 = 10100 and −7 = (11001) 2’s complement of 10100 = 01100
𝑪𝒐𝒖𝒏𝒕 𝑨 𝑸 𝑸−𝟏 𝑴 Operation
𝑛=5 0 0 0 0 0 1 1 0 0 1 0 1 0 1 0 0 Initial Values
0 1 1 0 0 1 1 0 0 1 0 𝐴←𝐴−𝑀
Arithmetic Right shift
Booths Multiplication Algorithm
 Example 3: Multiply −12 = 10100 and −7 = (11001) 2’s complement of 10100 = 01100
𝑪𝒐𝒖𝒏𝒕 𝑨 𝑸 𝑸−𝟏 𝑴 Operation
𝑛=5 0 0 0 0 0 1 1 0 0 1 0 1 0 1 0 0 Initial Values
0 1 1 0 0 1 1 0 0 1 0 𝐴←𝐴−𝑀
𝑛=4 0 0 1 1 0 0 1 1 0 0 1 Arithmetic Right shift
𝐴←𝐴+𝑀
Booths Multiplication Algorithm
 Example 3: Multiply −12 = 10100 and −7 = (11001) 2’s complement of 10100 = 01100
𝑪𝒐𝒖𝒏𝒕 𝑨 𝑸 𝑸−𝟏 𝑴 Operation
𝑛=5 0 0 0 0 0 1 1 0 0 1 0 1 0 1 0 0 Initial Values
0 1 1 0 0 1 1 0 0 1 0 𝐴←𝐴−𝑀
𝑛=4 0 0 1 1 0 0 1 1 0 0 1 Arithmetic Right shift
1 1 0 1 0 0 1 1 0 0 1 𝐴←𝐴+𝑀
Arithmetic Right shift
Booths Multiplication Algorithm
 Example 3: Multiply −12 = 10100 and −7 = (11001) 2’s complement of 10100 = 01100
𝑪𝒐𝒖𝒏𝒕 𝑨 𝑸 𝑸−𝟏 𝑴 Operation
𝑛=5 0 0 0 0 0 1 1 0 0 1 0 1 0 1 0 0 Initial Values
0 1 1 0 0 1 1 0 0 1 0 𝐴←𝐴−𝑀
𝑛=4 0 0 1 1 0 0 1 1 0 0 1 Arithmetic Right shift
1 1 0 1 0 0 1 1 0 0 1 𝐴←𝐴+𝑀
𝑛=3 1 1 1 0 1 0 0 1 1 0 0 Arithmetic Right shift
Arithmetic Right shift
Booths Multiplication Algorithm
 Example 3: Multiply −12 = 10100 and −7 = (11001) 2’s complement of 10100 = 01100
𝑪𝒐𝒖𝒏𝒕 𝑨 𝑸 𝑸−𝟏 𝑴 Operation
𝑛=5 0 0 0 0 0 1 1 0 0 1 0 1 0 1 0 0 Initial Values
0 1 1 0 0 1 1 0 0 1 0 𝐴←𝐴−𝑀
𝑛=4 0 0 1 1 0 0 1 1 0 0 1 Arithmetic Right shift
1 1 0 1 0 0 1 1 0 0 1 𝐴←𝐴+𝑀
𝑛=3 1 1 1 0 1 0 0 1 1 0 0 Arithmetic Right shift
𝑛=2 1 1 1 1 0 1 0 0 1 1 0 Arithmetic Right shift
𝐴←𝐴−𝑀
Booths Multiplication Algorithm
 Example 3: Multiply −12 = 10100 and −7 = (11001) 2’s complement of 10100 = 01100
𝑪𝒐𝒖𝒏𝒕 𝑨 𝑸 𝑸−𝟏 𝑴 Operation
𝑛=5 0 0 0 0 0 1 1 0 0 1 0 1 0 1 0 0 Initial Values
0 1 1 0 0 1 1 0 0 1 0 𝐴←𝐴−𝑀
𝑛=4 0 0 1 1 0 0 1 1 0 0 1 Arithmetic Right shift
1 1 0 1 0 0 1 1 0 0 1 𝐴←𝐴+𝑀
𝑛=3 1 1 1 0 1 0 0 1 1 0 0 Arithmetic Right shift
𝑛=2 1 1 1 1 0 1 0 0 1 1 0 Arithmetic Right shift
0 1 0 1 0 1 0 0 1 1 0 𝐴←𝐴−𝑀
Arithmetic Right shift
Booths Multiplication Algorithm
 Example 3: Multiply −12 = 10100 and −7 = (11001) 2’s complement of 10100 = 01100
𝑪𝒐𝒖𝒏𝒕 𝑨 𝑸 𝑸−𝟏 𝑴 Operation
𝑛=5 0 0 0 0 0 1 1 0 0 1 0 1 0 1 0 0 Initial Values
0 1 1 0 0 1 1 0 0 1 0 𝐴←𝐴−𝑀
𝑛=4 0 0 1 1 0 0 1 1 0 0 1 Arithmetic Right shift
1 1 0 1 0 0 1 1 0 0 1 𝐴←𝐴+𝑀
𝑛=3 1 1 1 0 1 0 0 1 1 0 0 Arithmetic Right shift
𝑛=2 1 1 1 1 0 1 0 0 1 1 0 Arithmetic Right shift
0 1 0 1 0 1 0 0 1 1 0 𝐴←𝐴−𝑀
𝑛=1 0 0 1 0 1 0 1 0 0 1 1 Arithmetic Right shift
Arithmetic Right shift
Booths Multiplication Algorithm
 Example 3: Multiply −12 = 10100 and −7 = (11001) 2’s complement of 10100 = 01100
𝑪𝒐𝒖𝒏𝒕 𝑨 𝑸 𝑸−𝟏 𝑴 Operation
𝑛=5 0 0 0 0 0 1 1 0 0 1 0 1 0 1 0 0 Initial Values
0 1 1 0 0 1 1 0 0 1 0 𝐴←𝐴−𝑀
𝑛=4 0 0 1 1 0 0 1 1 0 0 1 Arithmetic Right shift
1 1 0 1 0 0 1 1 0 0 1 𝐴←𝐴+𝑀
𝑛=3 1 1 1 0 1 0 0 1 1 0 0 Arithmetic Right shift
𝑛=2 1 1 1 1 0 1 0 0 1 1 0 Arithmetic Right shift
0 1 0 1 0 1 0 0 1 1 0 𝐴←𝐴−𝑀
𝑛=1 0 0 1 0 1 0 1 0 0 1 1 Arithmetic Right shift
𝑛=0 0 0 0 1 0 1 0 1 0 0 1 Arithmetic Right shift

Result
As MSB is 0, the result is positive 0 0 0 1 0 1 0 1 0 0 = (𝟖𝟒)𝟏𝟎
Booths Multiplication Algorithm
 Steps:
 Check the multiplicand and multiplier to be negative
 Negative (multiplier/multiplicand or both)– take 2’s complement of it
 Add sign bit in MSB
 Initialize A, Q, Q-1 M and Count
 Based on values of Q0,Q-1
 Perform A-M / A+M
 Arithmetic Right shift
 Decrease count

 Repeat until count = 0

Booths Multiplication Algorithm
 Example 3: Multiply −8 = 11000 and −9 = 10111 2’s complement of M = 01000
𝑪𝒐𝒖𝒏𝒕 𝑨 𝑸 𝑸−𝟏 𝑴 Operation
n=5 00000 10111 0 11000 Initial values
01000 10111 0 A-M
n=4 00100 01011 1 A. Right shift

n=0 00010 01000

Integer Division

 Division algorithm can be grouped into two classes according to their iterative operator.
 First Class
 Subtraction is the iterative operator
 Slow division as it’s execution time is proportional to the length of the operand (divisor)

 Second Class
 Obtain reciprocal of divisor and multiply the result by the dividend
 Two ways to find reciprocal
 Series expansion
 Newton-Raphson iteration
 Fast division
Integer Division

 Slow Division (Subtractive Algorithm)

 Division operation is defined as
𝑁
= (𝑄, 𝑅)
𝐷
 Where, 𝑁 = Numerator (Dividend), 𝐷 = Denominator (Divisor), 𝑄 = Quotient and 𝑅 = Remainder

Slow Division
Algorithm

Restoring Non-restoring
Binary Binary
Division Division
Integer Division

 Restoring Binary Division

 Load dividend and divisor values in register 𝑄 and 𝑀 respectively
 Initialize register 𝐴 to ‘0’
 Result of the division is place in 𝑛-bit 𝑄 register (quotient) and 𝑛-bit 𝐴 register (remainder)
 Start
Integer Division 𝐴←0
𝑀 ← 𝐷𝑖𝑣𝑖𝑠𝑜𝑟
𝑄 ← 𝐷𝑖𝑣𝑖𝑑𝑒𝑛𝑑
 Restoring Binary Division 𝑐𝑜𝑢𝑛𝑡 ← 𝑛

Left Shift 𝐴, 𝑄

𝐴←𝐴−𝑀

No Yes
𝐴<0
𝑄0 ← 0
𝑄0 ← 1
𝐴←𝐴+𝑀
𝑐𝑜𝑢𝑛𝑡 ← 𝑐𝑜𝑢𝑛𝑡 − 1

No Yes
𝑐𝑜𝑢𝑛𝑡 = 0 End
Fig. Flowchart for Restoring Division
Integer Division

 Restoring Binary Division

1. Load register 𝐴 with 0’s, 𝑄 with dividend and 𝑀 with 2’s complement of divisor
2. Shift 𝐴, 𝑄 left by 1 bit position.
3. Perform 𝐴 ← 𝐴 − 𝑀. This operation subtracts the divisor from the contents of register 𝐴.
4. If the result is
a. Non-negative ( MSB of 𝐴 = 0) then set 𝑄0 ← 1
b. Negative (MSB of 𝐴 = 1) them set 𝑄0 ← 0 and restore the previous value of 𝐴

5. Repeat step 2 through 4 as many times as there are bit positions in 𝑄

6. The remainder is in 𝐴 and the quotient is in 𝑄.
Integer Division
 Example 1: Divide using restore division method 7/3
Dividend : 𝑄 = (7)10 = (0111)2 Divisor : 𝑀 = (3)10 = (0011)2

Iteration 𝑨 𝑸 𝑶𝒑𝒆𝒓𝒂𝒕𝒊𝒐𝒏
0 0 0 0 0 0 1 1 1 Initial values
0 0 0 0 1 1 1 Left shift
1 1 0 1 1 1 1 A=A-M
1
1 1 0 1 1 1 1 0 LSB of Q = 0
0 0 0 0 1 1 1 0 Restore A
0 0 0 1 1 1 0 Left shift
1 1 1 0 1 1 0 A=A-M
2
1 1 1 0 1 1 0 0 LSB of Q = 0
0 0 0 1 1 1 0 0 Restore A
Integer Division
 Example 1: Divide using restore division method 7/3
Dividend : 𝑄 = (7)10 = (0111)2 Divisor : 𝑀 = (3)10 = (0011)2

Iteration 𝑨 𝑸 𝑶𝒑𝒆𝒓𝒂𝒕𝒊𝒐𝒏
2 0 0 0 1 1 1 0 0
0 0 1 1 1 0 0 Left shift
0 0 0 0 1 0 0 A=A-M
3
0 0 0 0 1 0 0 1 LSB 0f Q = 1

0 0 0 1 0 0 1 Left shift
1 1 1 0 0 0 1 A=A-M
4
1 1 1 0 0 0 1 0 LSB of Q = 0
0 0 0 1 0 0 1 0 Restore A (A=A+M)
 𝑨 𝑸
0 0 0 0 1 1 1 0
Integer Division 0 0 0 1 1 1 0
 Example 2: Divide 14/6 1 0 1 1 1 1 0
0 0 0 1 1 1 0 0
Dividend : 𝑄 = (14)10 = (1110)2
0 0 1 1 1 0 0
Divisor : 𝑀 = (6)10 = (0110)2
1 1 0 1 1 0 0
0 0 1 1 1 0 0 0
0 1 1 1 0 0 0
0 0 0 1 0 0 0
0 0 0 1 0 0 0 1
0 0 1 0 0 0 1
1 1 0 0 0 0 1
0 0 1 0 0 0 1 0
Integer Division

 Non-Restoring Binary Division

 The need to restore 𝐴 after unsuccessful subtraction is eliminated
 Provides improvement in calculations
 Initial Steps
 Load dividend and divisor values in register 𝑄 and 𝑀 respectively
 Initialize register 𝐴 to ‘0’

 Result of the division is place in 𝑛-bit 𝑄 register (quotient) and 𝑛-bit 𝐴 register (remainder)
Integer Division

 Non-Restoring Binary Division

1. Load registers with corresponding values 𝐴 with 0’s, 𝑄 with dividend and 𝑀 with 2’s complement of
divisor
2. Check the value of MSB of 𝐴
a. If MSB is 0, shift 𝐴, 𝑄 register to left by 1 position and perform 𝐴 ← 𝐴 − 𝑀
b. If MSB is 1, shift 𝐴, 𝑄 register to left by 1 position and perform 𝐴 ← 𝐴 + 𝑀
3. Again check the value MSB of 𝐴
a. If MSB of 𝐴 = 0, set 𝑄0 = 1
b. If MSB of 𝐴 = 1, set 𝑄0 = 0
4. Repeat step 2 and 3 for 𝑛 times.
5. After 𝑛 times, if MSB of 𝐴 is 1, then perform 𝐴 ← 𝐴 + 𝑀 to get proper positive remainder in 𝐴.
 Start B A
𝐴←0
𝑀 ← 𝐷𝑖𝑣𝑖𝑠𝑜𝑟 No
𝐶𝑜𝑢𝑛𝑡 = 0
𝑄 ← 𝐷𝑖𝑣𝑖𝑑𝑒𝑛𝑑
𝐶𝑜𝑢𝑛𝑡 ← 𝑛
Yes
No 𝑀𝑆𝐵 𝑜𝑓 𝐴 Yes No
=0 𝐴<0

Shift left 𝐴, 𝑄 Shift left 𝐴, 𝑄 Yes

𝐴←𝐴+𝑀 𝐴←𝐴−𝑀
𝐴←𝐴+𝑀

No 𝑀𝑆𝐵 𝑜𝑓 Yes
𝑀𝑆𝐵 = 𝐴0
=0
End
𝑄0 = 0 𝑄0 = 1
𝑄 = 𝑄𝑢𝑜𝑡𝑖𝑒𝑛𝑡
𝐶𝑜𝑢𝑛𝑡 ← 𝐶𝑜𝑢𝑛𝑡 − 1 𝐴 = 𝑅𝑒𝑚𝑎𝑖𝑛𝑑𝑒𝑟

B A Fig. Flowchart for Non-restoring Binary Division

Integer Division 𝒄𝒐𝒖𝒏𝒕 𝑨 𝑸 𝑴 𝑶𝒑𝒆𝒓𝒂𝒕𝒊𝒐𝒏
4 0000 1011 1101 Initial Values
 Eg. 1: Perform division using Non- 0001 011_ Shift left 𝐴, 𝑄
restoring method 11/3. 1110 𝐴←𝐴−𝑀
011_
 Dividend Q = (11)10 = (1011)2 3 1110 0110 𝑄0 = 0
 Divisor M = (3)10 = (0011)2 1100 110_ Shift left 𝐴, 𝑄
 2’s complement of M = 1101 1111 110_ 𝐴←𝐴+𝑀
2 1111 1100 𝑄0 = 0
 Quotient is (𝟎𝟎𝟏𝟏)𝟐 = (𝟑)𝟏𝟎 1111 100_ Shift left 𝐴, 𝑄
 Remainder is (𝟎𝟎𝟏𝟎)𝟐 = (𝟐)𝟏𝟎 0010 100_ 𝐴←𝐴+𝑀
1 0010 1001 𝑄0 = 1
0101 001_ Shift left 𝐴, 𝑄
0010 001_ 𝐴←𝐴−𝑀
0 0010 0011 𝑄0 = 1
𝑅𝑒𝑚𝑎𝑖𝑛𝑑𝑒𝑟 𝑄𝑢𝑜𝑡𝑖𝑒𝑛𝑡
 𝒄𝒐𝒖𝒏𝒕 𝑨 𝑸 𝟐′ 𝒔 𝒄𝒐𝒎𝒑𝒍𝒆𝒎𝒆𝒏𝒕𝑴 𝑶𝒑𝒆𝒓𝒂𝒕𝒊𝒐𝒏
Integer Division 5 00000 11101 11010 Initial Values
00001 1101_ Left Shift A,Q
 Eg. 1: Perform division using Non-
11011 1101_ A-M
restoring method 29/6.
4 11011 11010 LSB of Q =0
 Dividend Q = (29)10 = (11101)2
10111 1010_ Shift left
 Divisor M = (6)10 = (00110)2
11101 1010_ A+M
 2’s complement of M = 11010
3 11101 10100 LSB of Q =0
11011 0100_ Shift left
00001 0100_ A+M
2 00001 01001 LSB Of Q = 1
00010 1001_ Shift left
11100 1001_ A-M
1 11100 10010 LSB of Q = 0
11001 0010_ Shift Left
11111 0010_ A+M
0 11111 00100 LSB of Q=0
IEEE 754 Floating Point Representation

 Floating Point Representation

 A real number in binary will be represented in the following format
𝐼𝑚 𝐼𝑚−1 𝐼𝑚−2 … 𝐼2 𝐼1 𝐼0 . 𝐹1 𝐹2 … 𝐹𝑛 𝐹𝑛−1 𝐼𝑚 𝑎𝑛𝑑 𝐹𝑛 𝑎𝑟𝑒 𝑖𝑛𝑡𝑒𝑔𝑒𝑟 𝑎𝑛𝑑
𝑓𝑟𝑎𝑐𝑡𝑖𝑜𝑛 𝑝𝑎𝑟𝑡 𝑟𝑒𝑠𝑝𝑒𝑐𝑡𝑖𝑣𝑒𝑙𝑦

 A finite number can also represented by four integers components, a sign, a base (B), a significand (S),
and an exponent (E).
±𝑆 × 𝐵±𝐸
IEEE 754 Floating Point Representation

 Floating Point Representation

 Depending on base and the number of bits used to encode various components, the IEEE 754 standard
defines five basic formats.
 Among the five formats, the binary32 and the binary64 formats are single precision and double precision
formats respectively in which the base is 2.
IEEE 754 Floating Point Representation

 Single Precision Format of Floating Binary Number

 The single precision format has 23 bits for significand, 8 bits for exponent and 1 bit for sign.
 Base B is implicit and hence need not to be stored.

Sign of Biased exponent Significand

significand
8 bits 23 bits

 The leftmost bit stores the sign of the number ( 0 = 𝑃𝑜𝑠𝑖𝑡𝑖𝑣𝑒 , 1 = 𝑁𝑒𝑔𝑎𝑡𝑖𝑣𝑒 )
 The exponent value is stored in the next 8 bits. Biased representation is used.
 A fixed value, called as bias is added to the exponent to get biased exponent.
𝐵𝑖𝑎𝑠 = (2𝑘−1 − 1) … 𝑤ℎ𝑒𝑟𝑒 𝑘 = 𝑛𝑜. 𝑜𝑓 𝑏𝑖𝑡𝑠 𝑖𝑛 𝑡ℎ𝑒 𝑏𝑖𝑛𝑎𝑟𝑦 𝑒𝑥𝑝𝑜𝑛𝑒𝑛𝑡
 The final portion of the word (23 bits) is the significand.
IEEE 754 Floating Point Representation

 Single Precision Format of Floating Binary Number

 Examples: 1.1010010 × 210100
Exponent (e)
Significand/mantissa Base

𝑏𝑖𝑎𝑠 = 27 − 1 = 127 10100

𝐵𝑖𝑎𝑠𝑒𝑑 𝐸𝑥𝑝𝑜𝑛𝑒𝑛𝑡 𝐸 = 𝑒 + 127 +1111111
10010011

0 10010011 10100100000000000000000 1.5373952 × 220

IEEE 754 Floating Point Representation

 Single Precision Format of Floating Binary Number

 The sign bit is stored in the first bit of the word
 The first bit of the true significand is always 1 and need not to be stored in the significand field
 The value 127 is added to the true exponent to be stored in exponent field
 The base is 2
IEEE 754 Floating Point Representation

 Double Precision Format of Floating Binary Number

 The length of a double is 64 bits or 8 bytes.
 Doubles are encoded using the IEEE standard for normalized double-precision floating-point numbers.
 The double-precision floating-point data type is declared as ±𝑩𝑬 𝑺
 B is base 2

 E is exponent of the base 2. the exponent is biased by 1023

 S is fractional part of Significand in base 2

IEEE 754 Floating Point Representation

 Converting a number into Binary Single precision and Double precision format
 Floating point numbers are those where position of point is not fixed.
 To convert the given number into normalized form, apply normalization process
 Shifting the point either to left or right, so that there is only one non-zero digit to the left of point

 The obtained number is called as normalized number

 Normalized number is of the form
(−1)𝑆 × 2𝑒 × 1. 𝑀
 Where 𝑆 is sign of a number (S = 0 for +ve and 𝑆 = 1 for –ve)
 𝑒 is exponent

 𝑀 is mantissa or Significand
IEEE 754 Floating Point Representation

 Converting a number into Binary Single precision and Double precision format
1. Check the sign of a number.
2. Convert given decimal number into its equivalent binary number
3. Find out normalized number to get value of true exponent and mantissa/significand
4. Calculate the value of biased exponent using respective bias value
5. Convert calculated biased exponent into binary equivalent
6. Represent number in IEEE 754 format

S e M
IEEE 754 Floating Point Representation

 Converting a number into Binary Single precision and Double precision format

 E.g. Convert 85.125 into Single precision

 Convert 85 into binary number
85 10 = 1010101 2

 Convert 0.125 into binary number

0.125 × 2 = 0.250
0.250 × 2 = 0.500
0.500 × 2 = 1.000
0.125 10 = 001 2 Hence, 85.125 = 1010101.001 True Exponent
85.125 = 1.010101001 × 26
Sign = 0
Mantissa/Significand
IEEE 754 Floating Point Representation

 Converting a number into Binary Single precision and Double precision format

 E.g. Convert 85.125 into Single precision

85.125 = 1.010101001 × 26 Sign = 0
 Find biased exponent
True Exponent = 6 Bias = 127

So, Biased Exponent = 127 + 6 = 133

133 = 10000101
 Find Normalized Mantissa/Significand
010101001 The IEEE 754 Single precision is

 Add 0’s to complete the 23 bits

01010100100000000000000 0 10000101 01010100100000000000000

IEEE 754 Floating Point Representation

 Converting a number into Binary Single precision and Double precision format

 E.g. Convert -85.125 into Double precision

 Convert 85 into binary number 1.1010001
85 10 = 1010101 2

 Convert 0.125 into binary number

0.125 × 2 = 0.250
0.250 × 2 = 0.500
0.500 × 2 = 1.000
0.125 10 = 001 2 Hence, 85.125 = 1010101.001 True Exponent
85.125 = 1.010101001 × 26
Sign = 1
Mantissa/Significand
IEEE 754 Floating Point Representation

 Converting a number into Binary Single precision and Double precision format

 E.g. Convert -85.125 into Double precision

85.125 = 1.010101001 × 26 Sign = 1
 Find biased exponent
True Exponent = 6 Bias = 1023 So, Biased Exponent = 1023 + 6 = 1029
1029 = 10000000101
 Find Normalized Mantissa/Significand
010101001
 Add 0’s to complete the 52 bits 01010100100000000000000000000000000000000000000000
The IEEE 754 Double precision is

1 10000000101 01010100100000000000000000000000000000000000000000
 IEEE 754 Floating Point Representation

 Special Values
IEEE has reserved some values that can ambiguity.
 Zero – Zero is a special value denoted with an exponent and
mantissa of 0. -0 and +0 are distinct values, though they both
are equal.
 Denormalized – If the exponent is all zeros, but the mantissa
is not then the value is a denormalized number.
 Infinity – The values +infinity and -infinity are denoted with an
exponent of all ones and a mantissa of all zeros.
 Not A Number (NAN) – The value NAN is used to represent a
value that is an error. This is represented when exponent field
*For Double precision (just replacing 255 by 2049)
is all ones with a zero sign bit or a mantissa that it not 1
followed by zeros.