Basic Ops #4 – Division

I wasn’t sure whether to post this one or not. More over, my dilemma was whether to document this one or not. I decided that it’s so hard to explain what’s going on, that I will only dump my code here. The interface is ugly, because you cannot divide by zero…

// return success, *ret = a / b
int div(unsigned short a, unsigned short b, unsigned short *ret)
 if (b == 0) return 0;
 *ret = 0;
 unsigned short mask = 0, len = 0;

 // calc the mask of b.
 for (int i = 15; i >= 0; i–) {
  if (b & (1 << i)) {
  mask = (1 << i) – 1;
  len = 16 – i;
 // complement mask.
 mask = ~mask;

 // left justify b.
 while ((~b) & (1 << 15)) b <<= 1;

 while (len–) {
  *ret <<= 1;
  if ((a & mask) >= b) {
   *ret |= 1;
   a -= b;
  b >>= 1;
  mask >>= 1;

 return 1;

And yes it’s 16 bits division, it will apply for 32 or 64 bits as well. It really was one of the toughest things to write from scratch. Division is not that trivial like subtraction or multiplication. The trick eventually was to use the fact that we’re dealing with binary division..oh well, I quit. Get someone else to describe this one. Although I think there are many ways to implement this one. I remember a friend telling me he didn’t expect this way of solution. I don’t think, however, that this technique may be used for long division for bit array or really big numbers, maybe there’s something faster.

By the way, this is an unsigned division. As far as I know, and I might be wrong, you can’t do signed division without using unsigned division. And to do signed division you just remember the sign of a and b and then make them absolute and then you change the result accordingly. Anyways, if I’m wrong with my assumption, let me know otherwise.

3 Responses to “Basic Ops #4 – Division”

  1. Peter Ferrie says:

    You can do a signed division without div.
    You just extract the sign bits, convert the values to unsigned, do an _unsigned_ division, then apply the sign to the result.

  2. arkon says:

    Isn’t it what I said in the last paragraph? hmm

  3. Peter Ferrie says:

    Right, I had the “div” instruction in mind, which isn’t necessary. You can use your unsigned divide routine to achieve the result.
    Think of it as a confirmation. :-)

Leave a Reply