Insanely Low-Level

As promised, but in a long delay, the algorithm for Subtraction. Just notice how similar it is to the Addtraction algorithm. Also, try to think why we use the bitwise not operator to make it a borrow rather than carry.

unsigned int sub(unsigned int a, unsigned int b)
{
   a ^= b;
   b &= ~(a ^ b);
    while (b) {
       b <<= 1;
       a ^= b;
       b &= a;
    }
    return a;
}

After 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 dreaded Long Division algorithm. :)

Anyways, the intresting part about add and sub is that you cetainly will use the XOR operator. If you think of it, actually XOR can calculate add and sub together, but without fixing the carry or borrow. That you will have to do yourself. But it’s still good enough for one bit operations. For example: 1-1 = 0, and 1^1 = 0. Or another example, 1 + 0=1 –> 1^0=1. So this is all nice, but what happens when you have to borrow or to calculate the carry? So if you operate on 1 bit variables and you do 1+1, you will get 0 and a carry should be propagated to the next bit. Therefore, even if this is the case, we still can use the XOR operator, because 1^1 will yield a zero, which is what we expect. So now comes the big question – how do we calculate the carry (for now I will stick to carry, and later I will talk about borrow), the carry has to propagate from the low significant bit to the highest. In my opinion this is the most fascinating device in this algorithm, because the rest is the same for both add and sub.

So to answer that, let the input be two integers: a and b. Calculating the XOR between them is a good start and can be done as easily as that. But now we would like to fix the carry and apply it to the other bits. So if we AND (bitwise) the original a and b, we will get all parallel bits that match. For example, adding 2+6 will result in:

010 &
110
—-
010

This ANDed result is the mask of the carry we begin with. And I use the word “begin” since the carry has to propogate to the higher bits, and therefore we will need to iterate a specific operation that will fix the carry on the rest of the bits. The reason we AND a and b, is because surely the result’s bits are these which will cause a carry… Once we applied the current carry, we will have to calculate the next carry. As I said earlier, we have to iterate this operation, therefore it means there must be some condition which will stop this iteration, otherwise it won’t make any sense and stuck forever. Do you have any idea what will be this condition? It’s not the number of bits of a (aka sizeof a), nor b (which we presume are the same, of course). We will run as long as there is a carry to apply to the constructed result of the addition.

By now we know almost everything, there’s only one thing left out to be done, and that’s the actual calculation of the next carry. This is the most tricky thing in the whole algorithm. We have the mask of the carry from the a&b operation, every time we apply this mask by XORing it the result, we have to remove (mask off) these bits and continue until the carry-mask is zero. Therefore it is understandable that some bits should “go home”, but which bits do we remove? We have to remove the bits that were already applied as a carry (since carry changes after every bit). The real problem is that we need to calculate the carry for all bits at once, since we can’t and don’t want to calculate the carry for each bit, since it will be less optimized and not a challenge at all. But even then, it’s not possible to apply the carry only once, since it ‘carries’ to the next bit by ‘nature’.

Well, usually I think that when code is shown no words need to be spoken, but in the case of this algorithm, some text must be written. And that was the above…So now that you should know what’s going on abit, the code will help you to fully understand the algorithm. I never claimed to explain this algorithm well, it’s a really hard one, honestly. Sorry.

I will just remind you that XOR is the key to the add and sub operations. So if you take a look at the truth-tables of XOR, you will see that it is exactly what we need, like I tried to explain in the beginning. XOR alone is not enough to calculate the result of the wanted operation, since we have to apply the carry everytime. The carry is applied using, nothing else but, XORing again…you got that right.

unsigned int add(unsigned int a, unsigned int b) 
{ 
  a ^= b; // Do a one bit addition, now we have to calculate carry and apply it if required. 
  b &= a ^ b; // b will now contain the carry-mask, note that they are XORed again to eliminate a temporary value. 
  while (b) { // As long as there is a carry to apply to the result... 
     b <<= 1; // We've got to shift left, so the carry propagates to higher bits, right? 
     a ^= b; // Apply the new carry to the result. 
     b &= ~a; // Get the next carry-mask by removing bits that were already taken into account and fixed. 
  } 
  return a; 
}

If you really want to master this algorithm, start applying it on small number with 3 bits. You will see that the next carry is wisely calculated when you will begin with a carry that have a few bits set, for example: 7+5…

I will leave the implementation of the ‘sub’ to next week, so you can try to come up with it on your own. I can only say that it is really similar to the addition’s algorithm. Think of how you would change the carry into a borrow, and how it actually affects the mask.