Code your own division algorithm based on the long division algorithm you learned in grade school.
Take the 1 power of the denominator, and multiply onto the numerator
Take the logs of the numerator and denominator, subtract, and then raise the base of the log to that same power
@Jerry Coffin 20110322 05:58:20
The typical way is to shift and subtract. This is basically pretty similar to long division as we learned it in school. The big difference is that in decimal division you need to estimate the next digit of the result. In binary, that's trivial. The next digit is always either 0 or 1. If the (leftshifted) divisor is less than or equal to the current dividend value, you subtract it, and the current bit of the result is a 1. If it's greater, then the current bit of the result is a 0. Code looks like this:
unsigned divide(unsigned dividend, unsigned divisor) {
unsigned denom=divisor;
unsigned current = 1;
unsigned answer=0;
if ( denom > dividend)
return 0;
if ( denom == dividend)
return 1;
while (denom <= dividend) {
denom <<= 1;
current <<= 1;
}
denom >>= 1;
current >>= 1;
while (current!=0) {
if ( dividend >= denom) {
dividend = denom;
answer = current;
}
current >>= 1;
denom >>= 1;
}
return answer;
}
This works pretty much like when we do long division by hand. For example, let's consider 972/5. In decimal long division, we do something like this:
____
5)972
Then we figure each digit individually. 5 goes into 9 once, so we write down a 1 in that digit of the answer, and subtract 1*5 from (that digit) of the dividend, then "bring down" the next digit of the dividend:
1

5)972
5

47
We continue doing the same until we've filled in all the digits:
194

5)972
5

47
45

22
20

2
So, our answer is 194 remainder 2.
Now let's consider the same thing, but in binary. 972 in binary is 11 1100 1100, and 5 is 101. Now there is one fundamental difference between doing the division in binary vs. decimal: in decimal a particular digit could be anything from 0 to 9, so we had to multiply to find the intermediate result we were going to subtract from the dividend. In binary the digit is only ever going to be a 0 or a 1. We never need to multiply because we would only ever multiply by 0 or 1 (which we normally handle in an if statementeither we subtract or we don't).

101)1111001100
So, our first step is to figure out which will be the first digit in the result. We do that by comparing 101 to 1111001100, and shifting it left until it's greater. That gives us:

1111001100
10100000000
As we do that shifting, we count the number of places we've shifted so we know which digit of the result we're filling in at any given time. I've shown that with the vertical bar above. Then we shift the intermediate result right one place, and shift the vertical bar right with it to signify where we're doing to fill in a result digit:

1111001100
1010000000
From there we check if the shifted divisor is less than the dividend. If it is, we fill in a 1 in the proper place in the answer, and subtract the shifted divisor from the intermediate result [and to help keep columns straight, I'm going to insert some spaces]:
We continue the same way, filling in digits of the result, and subtracting the shifted divisor from the intermediate result until we've filled in all the digits. In a further attempt at helping keep things straight, I'm going to write in each digit of the result at the far right next to the subtrahend:
So, we get a result of 11000010, remainder 10. Converting those to decimal, we get the expected 194 and 2 respectively.
Let's consider how that relates to the code above. We start by shifting the divisor left until it's greater than the dividend. We then repeatedly shift it right and for each right shift check whether that value is less than the intermediate we got after the last subtraction. If it's less, we subtract again and fill in a 1 for that digit in our result. If it's greater, we "subtract 0" (don't do anything) and fill in a '0' for that digit in the result (which, again, doesn't require us to do anything, since those digits are already set to 0's).
When we've filled in all the digits, that's our result, and any amount left that we haven't subtracted yet is our remainder.
Some have asked why I used = instead of += in the code. I hope this helps explain why. Although in this case they produce the same result, I don't think of adding each digit to the existing partial answer. Rather, I think of it that spot in the answer as being empty, and the or just fills it in.
@Ahmed Nawar 20151001 23:55:34
it took me sometime to get the solution. Funny enough, to understand it I did the Khan Academy series on long division. It helped bridge some gaps.
In this algorithm (thanks for such detailed post), is there an issue with overflowing an int with left shift, when doing this portion " while (denom <= dividend) { denom <<= 1; current <<= 1; } Consider if we want to do 255 / 254 and let's assume we have 1 byte word. So this is FF / FE. In the first step, FE <= FF is true, so we do left shift of FE, which would have produced 1FC, but because 1 is chopped off, we got FC only, which is still <= FF, so we continue shifting, giving wrong current and denominator values too. Am I wrong? Need some protection against overflow?
@mlunoe 20160508 19:04:41
I like the solution here, but find the part harder to reason about. I created this solution, which makes more sense in my head: stackoverflow.com/a/37103688/1008519
@Edd 20170323 19:17:16
Does this actually work if the dividend is negative? Per your first if statement, I think that for any negative dividend and positive denom we return 0.
@Jerry Coffin 20170323 20:21:29
@Edward: Right now, this is basically for unsigned. Typically you want to note the signs of the inputs, divide positive numbers, then apply the correct sign to the result.
@Murillo Ferreira 20190709 13:11:07
Is this solution O(1)? Because the worst case is to shift left 32 times and shift right 32 times, which are both constants
@Jerry Coffin 20190709 14:01:38
@MurilloHenrique: It's O(N), where N is the number of bits in a word. So, if you're dividing 32bit numbers, it's limited to 32 shifts (in each direction). If you're dealing with 64bit words, it's 64 bits in each direction (and so on). I you prefer to think in terms of the magnitudes of the numbers that can be divided, it's O(log N).
@mlunoe 20160602 17:58:23
(This is a solution to the problem where you are not allowed to use multiplication either).
I like this solution: https://stackoverflow.com/a/5387432/1008519, but I find it somewhat hard to reason about (especially the part). This solution makes a little more sense in my head:
var divide = function (dividend, divisor) {
// Handle 0 divisor
if (divisor === 0) {
return NaN;
}
// Handle negative numbers
var isNegative = false;
if (dividend < 0) {
// Change sign
dividend = ~dividend+1;
isNegative = !isNegative;
}
if (divisor < 0) {
// Change sign
divisor = ~divisor+1;
isNegative = !isNegative;
}
/**
* Main algorithm
*/
var result = 1;
var denominator = divisor;
// Double denominator value with bitwise shift until bigger than dividend
while (dividend > denominator) {
denominator <<= 1;
result <<= 1;
}
// Subtract divisor value until denominator is smaller than dividend
while (denominator > dividend) {
denominator = divisor;
result = 1;
}
// If one of dividend or divisor was negative, change sign of result
if (isNegative) {
result = ~result+1;
}
return result;
}
Initialize the result to 1 (since we are going to double our denominator until it is bigger than the dividend)
Double the denominator (with bitwise shifts) until it is bigger than the dividend
Since we know our denominator is bigger than our dividend, we can subtract the divisor until it is less than the dividend
Return the recorded actions it took to get as close to the denominator as possible using the divisor
This is in O(n) not O(log(n)). It will take a lot of time for big numbers.
@grinsekatz007 20180425 20:39:33
If you take the division as a subtraction, what it basically is, you could use a method "decrement" what allows you to not use any operator at all, except for ~ at the end, to invert the result later into a positive integer or any other value.
private static int decrement(int i) {
System.out.println("Value of decrement : ");
System.out.println(i);
return i  1;
}
private static int divide(int n, int d) {
assert n > 0 && d > 0;
int counter = 0;
while (n >= d) {
for (int i = d; i > 0; i = decrement(i)) {
n = decrement(n);
}
counter = decrement(counter);
}
counter =~decrement(counter);
System.out.println(counter);
return counter;
}
@msbodw001 20170730 15:01:17
Simple Python implementation using basic high school math. A denominator is simply a number to the power of negative 1.
function divideWithoutDivision(a, b, precision) {
precision = precision > 0 ? precision : 10
var result = 0
var decimalPosition = 1
var A = a*0.1
var howManyTimes = 0
while (precision) {
A = A * 10
howManyTimes = 0
while (A >= b) {
A = A  b
howManyTimes += 1
}
result = result + howManyTimes*decimalPosition
decimalPosition = decimalPosition * 0.1
}
return result
}
document.write('<br>20/3 = ', divideWithoutDivision(20, 3))
document.write('<br>10/3 = ', divideWithoutDivision(10, 3))
document.write('<br>10/4 = ', divideWithoutDivision(10, 4))
document.write('<br>17/14 = ', divideWithoutDivision(17, 14))
document.write('<br>23/4 = ', divideWithoutDivision(23, 4))
It could be further improved by rounding after the last decimal place of the precision.
@Deepak Sharma 20140708 10:09:21
private int divideBy2(int number){
int count = 1;
while(count<=number){
if(count*2==number){
return count;
}
count++;
}
return count;
}
@Hemant 20131119 04:15:19
Following is the Java code for dividing number without using division operator.
private static int binaryDivide(int dividend, int divisor) {
int current = 1;
int denom = divisor;
// This step is required to find the biggest current number which can be
// divided with the number safely.
while (denom <= dividend) {
current <<= 1;
denom <<= 1;
}
// Since we may have increased the denomitor more than dividend
// thus we need to go back one shift, and same would apply for current.
denom >>= 1;
current >>= 1;
int answer = 0;
// Now deal with the smaller number.
while (current != 0) {
if (dividend >= denom) {
dividend = denom;
answer = current;
}
current >>= 1;
denom >>= 1;
}
return answer;
}
@AlienOnEarth 20140502 19:50:01
I am wondering will this algorithm also work when integers are negative values?
@Mrinal Shukla 20131021 18:10:41
Here is a simple divide method for ints without using a '/' operator:
public static int divide(int numerator, int denominator) throws Exception {
int q = 0;
boolean isNumPos = (numerator >= 0) ? true : false;
boolean isDenPos = (denominator >= 0) ? true : false;
if (denominator == 0) throw new Exception("Divide by 0: not an integer result");
numerator = Math.abs(numerator);
denominator = Math.abs(denominator);
while (denominator <= numerator) {
numerator = denominator;
q++;
}
return (isNumPos ^ isDenPos) ? q : q;
}
@rent 20131017 03:21:22
well, let's see... x/y = e^(ln(x)ln(y))
@michaelb958GoFundMonica 20131017 03:40:34
I'd think that two lns and a pow would usually be more expensive than one /.
@Zaza 20130410 00:10:44
The main concept :
Let's say we are calc 20/4, so
4*(1+1) = 8 *(1+1) = 16 *(1+1) == 32 (which is bigger) X
so go back to 16 and try 16*(1+0.5) == 24 (bigger) X
so go back to 16 and try 16*(1+0.25) == 20
Since the OP said it's an interview question, I think the interviewer wants to see the following things in addition to your coding skills. (Suppose you are using Java)
How to deal with negative numbers? It's common to convert both the dividend and the divisor to positive numbers. However, you may forget that Math.abs(Integer.MIN_VALUE) is still Integer.MIN_VALUE. Therefore, when the dividend is Integer.MIN_VALUE, you should calculate it separately.
What's the result of "Integer.MIN_VALUE/1"? There is no such value in Integer. You should discuss it with the interviewer. You can throw an exception for this condition.
public int divide(int dividend, int divisor) {
if(divisor == 0)
throw new Exception("Zero as divisor!");
int a = Math.abs(dividend);
int b = Math.abs(divisor);
boolean isPos = true;
if(dividend < 0) isPos = !isPos;
if(divisor < 0) isPos = !isPos;
if(divisor == Integer.MIN_VALUE){
if(dividend == Integer.MIN_VALUE) return 1;
else return 0;
}
if(dividend == Integer.MIN_VALUE) {
if(divisor == 1){
// the result is out of Integer's range.
throw new Exception("Invalid result.");
} else {
// Because Math.abs(Integer.MIN_VALUE) = Integer.MIN_VALUE
// we avoid it by adding a positive divisor to Integer.MIN_VALUE
// here I combined two cases: divisor > 0 and divisor < 0
return divide((dividend + b), divisor)  divisor/b;
}
}
int res = 0;
int product = b;
while(a >= b){
int multiplier = 1;
while(a  product >= product){
product = product << 1;// "product << 1" is actually "product * 2"
multiplier = multiplier << 1;
}
res += multiplier;
a = product;
product = b;
}
return isPos?res:res;
}
@philosodad 20110322 04:53:02
Well, if this is only integer/integer = int type division, it's pretty easy to get the integer part of x / n = int.dec by adding n+n+n+n until n is greater than x, then subtracting one from your 'n' count.
To get int/int = real without using *, /, %, or other math functions, you could do several things. You could return the remainder as a rational, for example. That has the advantage of being exact. You could also use string modification to turn your r into r0... (you pick the precision) and then repeat the same addition trick, then concatenate the results.
And of course, you could try having fun with bit shifting.
I don't know if this is so much a 'silly trick' as it is a test of how well you can use simple things (addition, subtraction) to build a complex thing (division). This is a skill that your potential employer might need, because there isn't an operator for everything. A question like this should (theoretically) weed out people who can't design algorithms from people who can.
I do think it's a problem that the answer is so readily available on the internet, but that's an implementation issue.
@Jim Dennis 20110322 04:21:38
Perhaps you can devise a way to do it using sequences of >> (bit shifts) with other bitwise operators. There's an example in psuedocode in the Wikipedia: Bitwise Operator article.
16 comments
@Rob Lachlan 20110322 03:55:37
Options:
@Jerry Coffin 20110322 05:58:20
The typical way is to shift and subtract. This is basically pretty similar to long division as we learned it in school. The big difference is that in decimal division you need to estimate the next digit of the result. In binary, that's trivial. The next digit is always either 0 or 1. If the (leftshifted) divisor is less than or equal to the current dividend value, you subtract it, and the current bit of the result is a 1. If it's greater, then the current bit of the result is a 0. Code looks like this:
This works pretty much like when we do long division by hand. For example, let's consider 972/5. In decimal long division, we do something like this:
Then we figure each digit individually. 5 goes into 9 once, so we write down a 1 in that digit of the answer, and subtract 1*5 from (that digit) of the dividend, then "bring down" the next digit of the dividend:
We continue doing the same until we've filled in all the digits:
So, our answer is 194 remainder 2.
Now let's consider the same thing, but in binary. 972 in binary is
11 1100 1100
, and 5 is101
. Now there is one fundamental difference between doing the division in binary vs. decimal: in decimal a particular digit could be anything from 0 to 9, so we had to multiply to find the intermediate result we were going to subtract from the dividend. In binary the digit is only ever going to be a 0 or a 1. We never need to multiply because we would only ever multiply by 0 or 1 (which we normally handle in an if statementeither we subtract or we don't).So, our first step is to figure out which will be the first digit in the result. We do that by comparing 101 to 1111001100, and shifting it left until it's greater. That gives us:
As we do that shifting, we count the number of places we've shifted so we know which digit of the result we're filling in at any given time. I've shown that with the vertical bar above. Then we shift the intermediate result right one place, and shift the vertical bar right with it to signify where we're doing to fill in a result digit:
From there we check if the shifted divisor is less than the dividend. If it is, we fill in a 1 in the proper place in the answer, and subtract the shifted divisor from the intermediate result [and to help keep columns straight, I'm going to insert some spaces]:
We continue the same way, filling in digits of the result, and subtracting the shifted divisor from the intermediate result until we've filled in all the digits. In a further attempt at helping keep things straight, I'm going to write in each digit of the result at the far right next to the subtrahend:
So, we get a result of 11000010, remainder 10. Converting those to decimal, we get the expected 194 and 2 respectively.
Let's consider how that relates to the code above. We start by shifting the divisor left until it's greater than the dividend. We then repeatedly shift it right and for each right shift check whether that value is less than the intermediate we got after the last subtraction. If it's less, we subtract again and fill in a
1
for that digit in our result. If it's greater, we "subtract 0" (don't do anything) and fill in a '0' for that digit in the result (which, again, doesn't require us to do anything, since those digits are already set to 0's).When we've filled in all the digits, that's our result, and any amount left that we haven't subtracted yet is our remainder.
Some have asked why I used
=
instead of+=
in the code. I hope this helps explain why. Although in this case they produce the same result, I don't think of adding each digit to the existing partial answer. Rather, I think of it that spot in the answer as being empty, and theor
just fills it in.@Ahmed Nawar 20151001 23:55:34
it took me sometime to get the solution. Funny enough, to understand it I did the Khan Academy series on long division. It helped bridge some gaps.
@Ahmed Nawar 20151007 23:14:11
This also helps regarding the basic concept homeschoolmath.net/teaching/md/long_division_why.php
@leonman30 20151015 18:32:56
In this algorithm (thanks for such detailed post), is there an issue with overflowing an int with left shift, when doing this portion " while (denom <= dividend) { denom <<= 1; current <<= 1; } Consider if we want to do 255 / 254 and let's assume we have 1 byte word. So this is FF / FE. In the first step, FE <= FF is true, so we do left shift of FE, which would have produced 1FC, but because 1 is chopped off, we got FC only, which is still <= FF, so we continue shifting, giving wrong current and denominator values too. Am I wrong? Need some protection against overflow?
@mlunoe 20160508 19:04:41
I like the solution here, but find the

part harder to reason about. I created this solution, which makes more sense in my head: stackoverflow.com/a/37103688/1008519@Edd 20170323 19:17:16
Does this actually work if the dividend is negative? Per your first
if
statement, I think that for any negative dividend and positive denom we return 0.@Jerry Coffin 20170323 20:21:29
@Edward: Right now, this is basically for unsigned. Typically you want to note the signs of the inputs, divide positive numbers, then apply the correct sign to the result.
@Murillo Ferreira 20190709 13:11:07
Is this solution O(1)? Because the worst case is to shift left 32 times and shift right 32 times, which are both constants
@Jerry Coffin 20190709 14:01:38
@MurilloHenrique: It's O(N), where N is the number of bits in a word. So, if you're dividing 32bit numbers, it's limited to 32 shifts (in each direction). If you're dealing with 64bit words, it's 64 bits in each direction (and so on). I you prefer to think in terms of the magnitudes of the numbers that can be divided, it's O(log N).
@mlunoe 20160602 17:58:23
(This is a solution to the problem where you are not allowed to use multiplication either).
I like this solution: https://stackoverflow.com/a/5387432/1008519, but I find it somewhat hard to reason about (especially the

part). This solution makes a little more sense in my head:Here are some test runs:
Here is a gist handling both the 0 divisor case and negative dividend and/or divisor: https://gist.github.com/mlunoe/e34f14cff4d5c57dd90a5626266c4130
@Parthiban Manoharan 20170709 17:11:50
Division of two numbers without using /
@das Keks 20180806 19:24:10
This is in O(n) not O(log(n)). It will take a lot of time for big numbers.
@grinsekatz007 20180425 20:39:33
If you take the division as a subtraction, what it basically is, you could use a method "decrement" what allows you to not use any operator at all, except for ~ at the end, to invert the result later into a positive integer or any other value.
@msbodw001 20170730 15:01:17
Simple Python implementation using basic high school math. A denominator is simply a number to the power of negative 1.
@Jonathon J Howey 20170929 20:24:44
This should be highest
@siva k 20160609 14:11:57
This is the function that solved my problem:
@Rao 20160609 14:19:07
May be, you want to add some explanation?
@trusktr 20160118 22:26:37
Here's one in JavaScript:
It could be further improved by rounding after the last decimal place of the precision.
@Deepak Sharma 20140708 10:09:21
@Hemant 20131119 04:15:19
Following is the Java code for dividing number without using division operator.
@AlienOnEarth 20140502 19:50:01
I am wondering will this algorithm also work when integers are negative values?
@Mrinal Shukla 20131021 18:10:41
Here is a simple divide method for ints without using a '/' operator:
@rent 20131017 03:21:22
well, let's see... x/y = e^(ln(x)ln(y))
@michaelb958GoFundMonica 20131017 03:40:34
I'd think that two
ln
s and apow
would usually be more expensive than one/
.@Zaza 20130410 00:10:44
The main concept :
Let's say we are calc
20/4
, soThe code:
@ChuanRocks 20130224 05:48:02
Since the OP said it's an interview question, I think the interviewer wants to see the following things in addition to your coding skills. (Suppose you are using Java)
How to deal with negative numbers? It's common to convert both the dividend and the divisor to positive numbers. However, you may forget that
Math.abs(Integer.MIN_VALUE)
is stillInteger.MIN_VALUE
. Therefore, when the dividend is Integer.MIN_VALUE, you should calculate it separately.What's the result of "Integer.MIN_VALUE/1"? There is no such value in Integer. You should discuss it with the interviewer. You can throw an exception for this condition.
Here is the Java code for this question and you can validate it leetcode:divide two integers:
@philosodad 20110322 04:53:02
Well, if this is only integer/integer = int type division, it's pretty easy to get the integer part of x / n = int.dec by adding n+n+n+n until n is greater than x, then subtracting one from your 'n' count.
To get int/int = real without using *, /, %, or other math functions, you could do several things. You could return the remainder as a rational, for example. That has the advantage of being exact. You could also use string modification to turn your r into r0... (you pick the precision) and then repeat the same addition trick, then concatenate the results.
And of course, you could try having fun with bit shifting.
I don't know if this is so much a 'silly trick' as it is a test of how well you can use simple things (addition, subtraction) to build a complex thing (division). This is a skill that your potential employer might need, because there isn't an operator for everything. A question like this should (theoretically) weed out people who can't design algorithms from people who can.
I do think it's a problem that the answer is so readily available on the internet, but that's an implementation issue.
@Jim Dennis 20110322 04:21:38
Perhaps you can devise a way to do it using sequences of >> (bit shifts) with other bitwise operators. There's an example in psuedocode in the Wikipedia: Bitwise Operator article.