Integer division without using the / or * operator

Question

I am going through an algorithms and datastructures textbook and came accross this question:

1-28. Write a function to perform integer division without using either the / or * operators. Find a fast way to do it.

How can we come up with a fast way to do it?

Answer 1

I like this solution: https://stackoverflow.com/a/34506599/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;
}

1. We initialize our result to 1 (since we are going to double our denominator until it is bigger than the dividend)
2. Double our denominator (with bitwise shifts) until it is bigger than the dividend
3. Since we know our denominator is bigger than our dividend, we can minus our divisor until it is less than our dividend
4. Return result since denominator is now as close to the result as possible using the divisor

Here are some test runs:

console.log(divide(-16, 3)); // -5
console.log(divide(16, 3)); // 5
console.log(divide(16, 33)); // 0
console.log(divide(16, 0)); // NaN
console.log(divide(384, 15)); // 25

Here is a gist of the solution: https://gist.github.com/mlunoe/e34f14cff4d5c57dd90a5626266c4130

Answer 2

Typically, when an algorithms textbook says fast they mean in terms of computational complexity. That is, the number of operations per bit of input. In general, they don't care about constants, so if you have an input of n bits, whether it takes two operations per bit or a hundred operations per bit, we say the algorithm takes O(n) time. This is because if we have an algorithm that runs in O(n^2) time (polynomial... in this case, square time) and we imagine a O(n) algorithm that does 100 operations per bit compared to our algorithm which may do 1 operation per bit, once the input size is 100 bits, the polynomial algorithm starts to run really slow really quickly (compared to our other algorithm). Essentially, you can imagine two lines, y=100x and y=x^2. Your teacher probably made you do an exercise in Algebra (maybe it was calculus?) where you have to say which one is bigger as x approaches infinity. This is actually a key concept in divergence/convergence in calculus if you have gotten there already in mathematics. Regardless, with a little algebra, you can imagine our graphs intersecting at x=100, and y=x^2 being larger for all points where x is greater than 100.

As far as most textbooks are concerned, O(nlgn) or better is considered "fast". One example of a really bad algorithm to solve this problem would be the following:

crappyMultiplicationAlg(int a, int b)
    int product = 0
    for (b>0)
        product = product + a
        b = b-1
    return product

This algorithm basically uses "b" as a counter and just keeps adding "a" to some variable for each time b counts down. To calculate how "fast" the algorithm is (in terms of algorithmic complexity) we count how many runs different components will take. In this case, we only have a for loop and some initialization (which is negligible in this case, ignore it). How many times does the for loop run? You may be saying "Hey, guy! It only runs 'b' times! That may not even be half the input. Thats way better than O(n) time!"

The trick here, is that we are concerned with the size of the input in terms of storage... and we all (should) know that to store an n bit integer, we need lgn bits. In other words, if we have x bits, we can store any (unsigned) number up to (2^x)-1. As a result, if we are using a standard 4 byte integer, that number could be up to 2^32 - 1 which is a number well into the billions, if my memory serves me right. If you dont trust me, run this algorithm with a number like 10,000,000 and see how long it takes. Still not convinced? Use a long to use a number like 1,000,000,000.

Since you didn't ask for help with the algorithm, Ill leave it for you as a homework exercise (not trying to be a jerk, I am a total geek and love algorithm problems). If you need help with it, feel free to ask! I already typed up some hints by accident since I didnt read your question properly at first.

EDIT: I accidentally did a crappy multiplication algorithm. An example of a really terrible division algorithm (i cheated) would be:

AbsolutelyTerribleDivisionAlg(int a, int b)
    int quotient = 0
    while crappyMultiplicationAlg(int b, int quotient) < a
        quotient = quotient + 1
    return quotient

This algorithm is bad for a whole bunch of reasons, not the least of which is the use of my crappy multiplication algorithm (which will be called more than once even on a relatively "tame" run). Even if we were allowed to use the * operator though, this is still a really bad algorithm, largely due to the same mechanism used in my awful mult alg.

PS There may be a fence-post error or two in my two algs... i posted them more for conceptual clarity than correctness. No matter how accurate they are at doing multiplication or division, though, never use them. They will give your laptop herpes and then cause it to burn up in a sulfur-y implosion of sadness.

Answer 3

I don't know what you mean by fast...and this seems like a basic question to test your thought process.

A simple function can be use a counter and keep subtracting the divisor from the dividend till it becomes 0. This is O(n) process.

int divide(int n, int d){
    int c = 0;
    while(1){
        n -= d;
        if(n >= 0)
            c++;
        else
            break;
    }
    return c;
}

Another way can be using shift operator, which should do it in log(n) steps.

    int divide(int n, int d){
    if(d <= 0)
        return -1;
    int k = d;
    int i, c, index=1;
    c = 0;
    while(n > d){
        d <<= 1;
        index <<= 1;
    }
    while(1){
        if(k > n)
            return c;
        if(n >= d){
            c |= index;
            n -= d;                
        }
        index >>= 1;
        d >>= 1;
    }
    return c;
}

This is just like integer division as we do in High-School Mathematics.

PS: If you need a better explanation, I will. Just post that in comments.

EDIT: edited the code wrt Erobrere's comment.

Answer 4

The simplest way to perform a division is by successive subtractions: subtract b from a as long as a remains positive. The quotient is the number of subtractions performed.

This can be pretty slow, as you will perform q subtractions and tests.

With a=28 and b=3,

28-3-3-3-3-3-3-3-3-3=1

the quotient is 9 and the remainder 1.

The next idea that comes to mind is to subtract several times b in a single go. We can try with 2b or 4b or 8b... as these numbers are easy to compute with additions. We can go as for as possible as long as the multiple of b does not exceed a.

In the example, 2³.3 is the largest multiple which is possible

28>=2³.3

So we subtract 8 times 3 in a single go, getting

28-2³.3=4

Now we continue to reduce the remainder with the lower multiples, 2², 2 and 1, when possible

4-2².3<0
4-2.3 <0
4-1.3 =1

Then our quotient is 2³+1=9 and the remainder 1.

As you can check, every multiple of b is tried once only, and the total number of attempts equals the number of doublings required to reach a. This number is just the number of bits required to write q, which is much smaller than q itself.

Answer 5

unsigned bitdiv (unsigned a, unsigned d)
{
unsigned res,c;

for (c=d; c <= a; c <<=1) {;}

for (res=0;(c>>=1) >= d; ) {
        res <<= 1;
        if ( a >= c) { res++; a -= c; }
        }
return res;
}

Answer 6

This is not the fastest solution, but I think it's readable enough and works:

def weird_div(dividend, divisor):
    if divisor == 0:
        return None

    dend = abs(dividend)
    dsor = abs(divisor)
    result = 0
    
    # This is the core algorithm, the rest is just for ensuring it works with negatives and 0
    while dend >= dsor:
        dend -= dsor
        result += 1
    
    # Let's handle negative numbers too
    if (dividend < 0 and divisor > 0) or (dividend > 0 and divisor < 0):
        return -result
    else:
        return result

# Let's test it:
print("49 divided by 7 is {}".format(weird_div(49,7)))
print("100 divided by 7 is {} (Discards the remainder) ".format(weird_div(100,7)))
print("-49 divided by 7 is {}".format(weird_div(-49,7)))     
print("49 divided by -7 is {}".format(weird_div(49,-7)))   
print("-49 divided by -7 is {}".format(weird_div(-49,-7)))   
print("0 divided by 7 is {}".format(weird_div(0,7)))         
print("49 divided by 0 is {}".format(weird_div(49,0)))

It prints the following results:

49 divided by 7 is 7
100 divided by 7 is 14 (Discards the remainder) 
-49 divided by 7 is -7
49 divided by -7 is -7
-49 divided by -7 is 7
0 divided by 7 is 0
49 divided by 0 is None

Answer 7

The pseudo code:

count = 0
while (dividend >= divisor) 
    dividend -= divisor
    count++
//Get count, your answer