Binary addition

Let's take a look at how binary addition can be done by using bitwise operations. Why would we want to do this? Simply because we  can. And also because it's fun and will help us understand how bitwise operations work and can be used together.

public byte AddBytes(byte a, byte b) {
    while (b != 0) {
        var carryBits = (byte) (a & b);
        a = (byte) (a ^ b);
        b = (byte) (carryBits << 1);
    }
    return a;
}

Let's take an overview of what just happened.

Essentially we add two bytes together. You get that much from the name of the method.

The signature of the AddBytes method also tells us that it takes in two bytes, a and b as parameters, and returns a byte which contains the result of the addition.

Inside the method we loop until b is zero. Inside the while loop we AND (&), then we XOR (^), and finally we left shift (<<) by one.

And, apparently, as a result we get two binary numbers added together nicely, just like in our everyday base-10, where we could calculate something like 2 + 2 = 4 

So why does the above piece of code work and do what it does? Let's break it down and make it simple.

The first operation inside the while loop is storing temporarily in carryBits variable the result of the bitwise AND (&) operation between a and b, ie:

var carryBits = (byte) (a & b);

There's a little bit of casting going on here through and through because C# doesn't support performing bitwise operations directly on the actual byte type, it converts them for the bitwise operations. You could also perform these operations on the int type, for example, in which case you would have:

var carryBits = a & b;

Don't get distracted by the casting.

So, we're carrying bits. But what is carrying? Let's take a quick refresher on carrying in math. Carrying is just like in normal everyday addition:

   122
+  921
= 1043

Where you add the numbers together which are on top of each other and you combine them at the bottom for the final result. You have the ones, you have the tens, you have the hundreds, and you have the thousands. In the same way in binary you have the ones, you have the twos, you have the fours, you have the eights, and so on. It's just base-2 (0, and 1) instead of base-10 (0, 1, 2, 3, 4, 5, 6, 7, 8, and 9) before the numbers flip over to the next scale.

In the above example carrying happens when you add the one hundred and nine hundred together, you carry the one to the thousands and in hundreds you then have a zero because 100 + 900 doesn't leave a remainder in the hundreds. If you had 100 + 1100 instead you  would add the thousands: 0 * 1000 + 1 * 1000 = 1000, and then you would add the hundreds: 1 * 100 + 1 * 100 = 200. And finally you would add all the different values together (no more carrying to process) and you'd end up with a total of 1200.

So carrying happens when you add two numbers together (for example 9 + 9) and they don't fit in the scale (in this case the ones) and you have to move, ie. you'd have to carry, the overflow to the tens. You'd end up with 18.

In binary it works in exactly the same way. When you get overflow from addition you move it up, you carry it over.

The only differences are that in binary you, usually, go from right to left, and 0 means that the value isn't set, and 1 means the value is set. Therefore:

1101

Simply means, from right to left:t 1 * 1 + 0 * 2 + 1 * 4 + 1 * 8. From right to left -> ones (set), twos (not set), fours (set), eights (set). Giving us the total of 13 in our every day base-10.

var a = (byte) 0b_0101; // (This is a "binary literal" in C#)
var b = (byte) 0b_0110;
var carryBits = (byte) (a & b);

So, when we do a bitwise AND operation, like 0101 & 0110(as shown in the above example) simply imagine in your head that you place the numbers on top of each other like in regular base-10 calculus:

  0101
& 0110
= 0100

The bitwise AND operation returns 1 only when the two overlapping binary numbers are both 1. For all other binary values it returns 0.

So why are we doing this and storing the result in carryBits? Because it's exactly the same as when you add 100 + 900, you know you need to carry the hundreds into thousands, except now you need to carry the overflowing bits. Now we know that there are overlapping values, and when we add them together we will need to carry this bit position to the next one.

It should be starting to make sense now. Let's move on.

a = (byte) (a ^ b);

Here we are storing the result of an XOR (^) operation between a and b in the a. We are basically simulating addition with XOR.

What XOR does is:

  0101
^ 0110
= 0011

 It returns 1 only when the two bits that are being compared are different from each other.

We have already safely stored the overflowing bits in the temporary carryBitsand now we have copied the rest of the bits which are not overflowing (no need to carry anything) to a.

We can now perform the final bitwise operation which is the left bitshift. What left bitshift does is that it simply moves all the bits left by whatever number you want to move them. For example:

  var a = (byte) 0b_0001; // a is 0001
  a = a << 1;             // a is 0010
  a = a << 1;             // a is 0100
  a = a << 1;             // a is 1000
  a = a << 1;             // a is 0000

In the final left bitshift operation we lose our data. By default we get behavior which simply drops overflowing bits - you lose them, they are gone.

And if you move it by two:

var a = (byte) 0b_0001; // a is 0001
a = a << 2;             // a is 0100

 The bits are simply shifted left by two positions.

By now you might be starting to realize "Wait... but what if I have an overflow, carry bit, at position like:

1000

Where there is nowhere to go?" 

That's right. In that kind of situations you would get an incorrect answer from bitwise binary addition. For simplicity's sake this article doesn't show you how to handle situations like that where you actually run out of space from your value type. It can be handled, but the code gets much more complex and is therefore not a very good place to show the basic principles of binary bitwise addition and is therefore out of the scope of this article.

b = (byte) (carryBits << 1);

Now that you understand what a left bitshift does, it's not hard to see what's going on here. We're simply moving the carry bits, the overflowing bits, one step further in the scale of numbers. One becomes two, two becomes four, and so on.

We assign the result into b, all the numbers in b just moved one step left. The while loop is now ready for another round until there are no more 1 bits left in b.

When b is zero we're ready to exit the while-loop and return a where we have shifted, combined, and shuffled all of our bits iteration by iteration. We're moving and fitting everything together in a nice and orderly line of bits.

Logic! There's nothing better.

If you don't understand binary addition straight away by simply reading this article, don't fret. There's hope for you yet. It's like driving a bicycle. You don't learn how to drive by simply reading a manual. Once you understand the basic principles of binary bitwise operations you have to play with them, and experiment with them.

That's how you learn.