Quick way to do Two's Complement

This might be relatively simple to figure out by one’s self, but this has definitely helped me save a lot of time on exams and I think it’s worth explicitly writing about. So here it is!

So, what is Two’s Complement? Essentially, it’s an ingenious way of representing negative numbers using only the numbers 1 and 0. This is very useful because when it comes down to it, all modern day computers use 1’s and 0’s for all of their calculations, so it’s handy to be able to calculate things using negative numbers!

So how does Two’s Complement work, let’s say for the number -29? The first step is to take the absolute value of the number and represent it in binary form. Then, simply invert the bits and add one.

So what’s the advantage of using Two’s Complement? Well, it makes calculations involving negative and positive numbers REALLY FAST, since everything just boils down to simple bit operations. For example, if you added 29 + -29:

If you ignore the overflow in this case, you would have 0 as the outcome. Because Two’s Complement makes everything so convenient, it is regarded as a universal way of storing negative numbers in binary notation. In fact, I would say it would be pretty hard to find a computer that didn’t use Two’s Complement these days.

Good question. Let’s first ask ourselves what the calculation involves:

Okay, seems pretty straightforward. Writing the positive absolute value in binary is relatively trivial if you keep dividing the number by 2 repeatedly and saving the remainders as you go. There’s probably no easy way around the conversion, so we’ll leave that there for now.

What about the last two parts, inverting and then adding 1? Inversion and adding one themselves are trivial, and sure, you can do both, but notice what happens when you add one to an already inverted number:

That’s right, you end up getting the number you originally started with, ignoring overflow! So, the critical question here is that if adding one to an inverted number returns the original number, why would you invert this number if it doesn’t need to be inverted?

It’s a little hard to see where I’m going at here, so let’s apply this observation to another example, let’s say -16.

Let’s compare -16 in Two’s Complement with 16 in binary form. We’ll use a XNOR function to pick out only the bits that match each other:

Here is the critical observation: it looks like that the places with 1 as a bit are the bits that go unchanged in the Two’s Complement conversion. These bits happen to be where the last 1 bit is in the absolute binary form, going from left to right. Everything up to that one bit seems like it is inverted.

So, let’s revise the Two’s Complement algorithm using this heuristic.

Let’s try this with -28:

Well, it looks like this heuristic works for -28, but will it work for any number n? Well, not using a formal proof, any number you flip and add 1 to will become the original number, with an overflow of 1. So if you go to the last 1 bit when examining a binary number (going from left to right), you can treat that 1 as the overflow to the bits you are keeping consistent. That’s why you only need to invert part of a number up up to it’s last 1 bit: if those bits are going to stay the same anyway, there’s no point in flipping those bits at all!

Since this will work for any binary number, we can change this from a heuristic to an algorithm :)

Some more examples:

Hope this will save you some time on exams! (Or the times you actually need to calculate Two’s Complement, haha.)

Note: Shout out to my CSE 30 Professor Rick Ord for opening my eyes to this in like 2014 ^.^