Insanely Low-Level

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;
  break;
  }
 }
 // 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.

This entry was posted on Saturday, March 1st, 2008 at 3:56 pm and is filed under Algorithms. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.