Division of two numbers without using division operator, Algorithm, C - Code

Saturday, January 24, 2009

I was asked for the C solution for this by some of my friends, the code for division of two numbers without using the division operator, even though I had written about it in my sun blog using python, this time I would like to explain the code for division of two numbers without divide operator using the C language which would be useful for C fans as well.

For the sake of completeness, I would like to highlight the algorithm, which is quite simple. Before that one should understand some basics of bit shifting.

1. Left shifting an unsigned number by 1 multiplies that number by 2.
2. Right shifting an unsigned number by 1 divides that number by 2.

Therefore the procedure for the division algorithm, given a dividend and a divisor would be to left shift (multiply by 2) the divisor till it reaches dividend/2, then continue this routine with the the difference between the dividend and divisor and divisor till the point where dividend is less than divisor or their difference is zero. This is similar to finding an element in a sorted list using the binary search algorithm, the C code is furnished below.

Listing 1: division_bitshifting.c

 1: /* 
2: Division of two numbers without using division operator
3: Author: S.Prasanna
4: */
5:
6: #include<stdio.h>
7:
8: int dividend, divisor, remainder;
9:
10: /* Division function Computes the quotient and remainder of two numbers
11: using bit shifting */
12: int division(int tempdividend, int tempdivisor) {
13:
14: int quotient = 1;
15:
16: if (tempdivisor == tempdividend) {
17: remainder = 0;
18: return 1;
19: } else if (tempdividend < tempdivisor) {
20: remainder = tempdividend;
21: return 0;
22: }
23:
24: while (tempdivisor <= tempdividend) {
25: /* Here divisor <>
26: divisor and quotient */
27: tempdivisor = tempdivisor << 1;
28: quotient = quotient << 1;
29: }
30:
31: /* We have reached the point where divisor > dividend,
32: therefore divide divisor and quotient by two */
33: tempdivisor = tempdivisor >> 1;
34: quotient = quotient >> 1;
35:
36: /* Call division recursively for the difference to get the
37: exact quotient */
38: quotient = quotient + division(tempdividend - tempdivisor, divisor);
39:
40: return quotient;
41: }
42:
43: /* Division of two numbers without using division operator */
44: void main() {
45:
46: printf ("\nEnter the Dividend: ");
47: scanf("%d", &dividend);
48: printf("\nEnter the Divisor: ");
49: scanf("%d", &divisor);
50:
51: printf("\n%d / %d: quotient = %d", dividend, divisor, division(dividend, divisor));
52: printf("\n%d / %d: remainder = %d", dividend, divisor, remainder);
53: getch();
54: }
The algorithm explanation is very simple, the division function in line 12 is a recursive procedure which implements the division logic described above using bit shift operators, the best way to understand it would be to execute the above division algorithm with break points or debuggers to track the flow.

12 comments:

Anonymous said...

Can your algorithm handle cases where either the divisor or the dividend is negative ?

Anonymous said...

getting the quotient and remainder is very easy. the real problem is to get values like 3/2=1.5

harit said...

I like it! easy to understand the way you have written

Alma Mae said...

help me pls...
create a function divide and remainder without using the operators / and %. Then create a program that use those functions.

Anonymous said...

WHy all this?

int reminder;

int DIV(int x, int y)
{
int q = 0;
while (x > y) {
x -= y;
q++;
}
reminder = x - (y*q);
return q;
}

Anonymous said...

plz send ur email address.
mine is
deed_gsdgsg@yahoo.com

Saurabh Raisinghaney said...
This comment has been removed by the author.
Saurabh Raisinghaney said...
This comment has been removed by the author.
Saurabh Raisinghaney said...

The binary shift will yield result in approx O(log n) time while the regular rotation may be a lot slower...


try 100,000 / 3
quotient 333,333 and remainder 1
it will take : 333,333 loops to get to the answer with regular approach in one of the above comment, but with binary shift...may be in 100 iterations we will reach to the answer...

Anonymous said...

i've been confused since i red your program, how did the remainder get its value when the tempdividend > tempdivisor....

Anonymous said...

How to perform the division without using division or modulus operator (%,/)and without using loop or recursion. Please let me know.Thanks in advance.

kudination said...

How can you put these into an algorithm


Copyright © 2008 Prasanna Seshadri, www.prasannatech.net, All Rights Reserved.
No part of the content or this site may be reproduced without prior written permission of the author.