Division without using '/'

Question

Can anyone tell me an efficient approach to perform the division operation without using '/'. I can calculate the integer value in log(n) steps using a method similar to binary search.

115/3 
57 * 3 > 115
28 * 3 < 115
47 * 3 > 115
.
.
.
38 * 3 is quotient value .....

But is there any other more efficient method?

Answer 1

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 (left-shifted) 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 statement--either 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]:

            1  
     -----------------------------
  101)1  1  1  1  0  0  1  1  0  0
      1  0  1  0  0  0  0  0  0  0
      ----------------------------
         1  0  1

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:

            1  1  0  0  0  0  1  0
     -----------------------------
  101)1  1  1  1  0  0  1  1  0  0
      1  0  1                             1
      -----------------------------
         1  0  1
         1  0  1                           1
      -----------------------------
            0  0  0                          0
         --------------------------
               0  0  0                        0
          -------------------------
                  0  0  1                      0
          -------------------------
                     0  1  1                    0
          -------------------------
                        1  1  0   
                        1  0  1                   1
           ------------------------
                           0  1  0                 0

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.