A few years a go a friend challenged me to write the basic arithmetic operations, add/sub, div/mul. But the catch was to write them without using that same instruction for doing the calculation and to make it as a long multiplication rather than log(A*B). I think the Multiply implementation is the easiest one amongst these operations, so I decided to start with it:
unsigned int mul(unsigned int a, unsigned int b)
{
unsigned int sum = 0, d = 0;
while (a) {
if (a & 1) sum += (b << d);
a >>= 1;
d++;
}
return sum;
}
The idea of the algorithm, which I wrote from scratch, was to treat the input A as a mask. And anytime the next bit is set in the mask, I accumulate the shifted B. So what you get actually is long multiplication, which will work for negative numbers as well as positive ones, since the nature of 2’s complement numbers.
You should take a paper and a pencil and start playing with the algorithm by applying it on small numbers and learn how it works… :) Though this one is easy, really.
[…] we started with the really easy implementation of Multiplication’s algorithm (right here), I will now proceed to add and sub, which are a bit more complicated. But still, nothing like the […]