One’s and Two’s Complement

As we have already seen, binary numbers are organized as bits of 1s and 0s. Each individual bit’s position has its own value, this is referred to as the bit’s place-value, and this value is in the mathematical form of the powers of 2.
The first bit from right, which we know is in the Ones Position, is called as an LSB or the Least Significant Bit.
And, the last bit on the left, which in the above image is in the 128s position, is called as an MSB, or the Most Significant Bit.

Let’s again look at a binary number. By now we should be able to easily tell that the decimal value of this binary number should be…
1x4s + 1x1s = 5

In the previous article, we talked about addition and subtraction of binary numbers. But, how can we represent a negative binary number?

A complement of a number is, in fact, the opposite of that number.
So, In a Decimal numbering system :

The complement of      7  would be -7
And, the complement of 27 would be -27

And, what is obvious about the complements is that when we add the complements together we get a 0

So, as in the above example.
7 + (-7) = 0
27 + (-27) = 0

So, you might say, well, if the above is true then…

The complement of a binary number 0101 would be -0101

And surely enough
0101 + (-0101) = 0

And you would be absolutely right!

But! this is not how a computer works…

A computer stores data in, what is called as Registers.
A register is a group of flip-flop switches, arranged in the configuration of 8, 16, 32, or 64 bits. 
So, the above image would represent an 8-Bit Register.
And, unfortunately, this is the only place that the computer has to store a piece of data.
A flip-flop switch can only have two states. It can either be ON or be OFF. Reminds you of something? Of course, a binary number!
A register stores a binary number by configuring the flip-flop switches in an appropriate sequence.
So, as you can guess, a register trying to store a number 101, would have its switches in the 1st and the 3rd position from the right, set to ON, and all other switches set to OFF.

So, well, if we have to represent a number using only the switches in the register, then how can we represent a negative number?

There are a couple of ways. Let’s take a look.


Sign and Magnitude

When we are representing a negative number, we are in fact providing two sets of information.

The sign indicates the direction, and the value indicates the magnitude.

With reference to the above number line, when we say a value is negative, we are actually referring that the value lies on the Left side, and vice-versa.

Using the same understanding, if we want to represent a binary number in a register, we just need a way to provide these two sets of information, viz. the Direction and the Magnitude.

And, this can be achieved by reserving the MSB as a sign-bit.

So, now, we have the left-most bit representing the sign, and all other bits represent the magnitude.

0 in the MSB will represent a positive value
1 in the MSB will represent a negative value

So, the number 5 and its complement in binary using an 8-Bit register would be...

00000101 = +5
10000101 = -5

And the same number using a 4-Bit register would be...

0101 = +5
1101 = -5

It is important that we know the size of the register that we are working with. This will govern the position of the MSB, and thus, the position of the Sign-Bit.

For 8-Bit registers, the sign-bit has a place-value 2^8 = 256s
For 4-Bit registers, the sign-bit has a place-value 2^4 = 16s

With this in mind, let’s jot down the complements side-by-side for a 4-Bit register.

As you can see, reserving the MSB for a sign-bit leaves us with 3 usable bit for the magnitude.

So, flipping the sign-bit to 1,  0 becomes -0, 1 becomes -1…

Sorry, what?!
Did we just say, 0 becomes – 0?

Well, indeed…

0 in Binary = 0000
So with the concept of Sign and Magnitude, if we flip the MSB from 0 to 1 for representing a negative number, we get...
-0 in Binary = 1000

Ok, well, we need to fabricate some method to represent a negative number, and surely, that would also inject some discrepancy. And, either way, 0 and -0 are actually one and the same, so that won’t be too bad… or is it?

Let’s take a closer look…

As we said earlier, the property of complements is that when we add them together, they cancel each other and we get a 0.

5 + (-5) = 0
So, 0101 + 1101 Should also be 0
Let's do the math...

1 + 1 = 10 -> Keep 0, carry over 1
0 + 0 + 1 carried over = 1 -> Keep 1,
1 + 1 = 10 -> Keep 0, carry over 1
0 + 1 + 1 carried over = 10 -> Keep 0, carry over 1

Our register supports only 4 bits, and we are already at the 4th bit, but we still have 1 carried over... and we don't have any space to accommodate it...
We clearly have an overflow, and unfortunately have to discard that extra bit.

But, look closely.
We were expecting the result to be 0000.
But, even with a discarded bit, the result of adding two complements is surprisingly 0010, that is 2 in decimal!

Surely enough, there is a flaw in our assumption. This method does not work. You may try for yourself.

Try adding 7 and the complement of 3
7 + (-3)
0111 + 1011
You would expect the result to be 0100 or 4 in decimal
But, actually we get 0010 or 2 in decimal...

That’s absolutely unacceptable!

A sign and magnitude notation may appeal to us as humans, but clearly, it does not go well with computers.

Let’s look at a different approach.


One’s Complement

One’s complement suggests that we form a negative number by taking the positive number and inverting every bit.

For example, 
We form the one's complement of 3, by inverting each of its bits.
3 = 0011
-3 = 1100


So, as before, let’s jot down the complements side-by-side.

We still have the benefits of the sign-bit, 0 representing a positive, and 1 representing a negative number.
But what we are actually doing here is mapping the unsigned binary number 15 into representing a -0.
So, we still have the problem of two representations of 0.
But, let’s see how it performs on the addition of the complements.

Let's again try to add together the complements of 5.

5 + (-5) = 0
Let's do the math..
1 + 0 = 1
0 + 1 = 1
1 + 0 = 1
0 + 1 = 1

And, we get 1111, which, as per our above chart is -0
Yes, -0, but that's still way better that the previous method.
Let's also try
7 + (-3) = 4
So,
0111 + 1100
Let's do the math.
1 + 0 = 0 -> Keep 0
1 + 0 = 0 -> Keep 0
1 + 1 = 10 -> Keep 0, carry over 1
0 + 1 + carried 1 = 10 -> Keep 0, carry over 1

Till now we get 0011

But, again as before, we have an overflow, because our register supports only 4-Bits.

In these cases,
Ones Complement suggests that, if the addition generates an overflow bit, then don't discard it, but bring it back and add it to the result.

So,
0011 + 1 = 0100, And that's 4!

That’s amazing!

One’s Complement passes the addition test in both the cases, well quite close.
We still have the problem of two representations of 0, and we also have to do this extra addition with the overflow bit.

Let’s look into the solution


The Two’s Complement

A Two’s Complement is equivalent to One’s Complement, with 1 added in.

To elaborate, for generating a two’s complement of a binary number, we first turn that number to its one’s complement by flipping the bits and then add 1 to it.

For example, to form a two's complement of 3...
We first form the one's complement by flipping all the bits.
And, then add 1

3 in binary = 0011
-3 in 1's comp. = 1100
-3 in 2's comp. = 1101

So, what does that do to our two representations of 0?

0 in binary    = 0000
0 in 1's comp. = 1111
0 in 2's comp. = 1111 + 1
So, if we do the math, we will see that we again have an overflow.
But...
Two's Complement suggests that, if an addition generates an overflow bit, just discard it, and you should be perfectly fine!

And look! We now get a 0
There's no more a -0, it's just 0

We have finally eliminated our first problem, we now have just a single representation of 0.

As usual, let’s jot down the complements side-by-side.

Now, let’s see how it performs at our complement addition test.

5 + (-5) = 0
So, let's add
1 + 1 = 10 -> Keep 0, carry over 1
0 + 1 + carried 1 = 10 -> Keep 0, carry over 1
1 + 0 + carried 1 = 10 -> Keep 0, carry over 1
0 + 1 + carried 1 = 10 -> Keep 0, carry over 1

We are now at the last bit, and we again have an overflow. But, as stated above, we can safely discard the overflow bit.

And we get 0!
We are no more getting a -0, it is a super sweet 0!

Just what we wanted!

Let’s take one more example

7 + (-3) = 4
let's add
0 + 1 + = 10 -> Keep 0, carry over 1
1 + 0 + carried 1 = 10 -> Keep 0, carry over 1
1 + 1 + carried 1 = 11 -> Keep 1, carry over 1
0 + 1 + carried 1 = 10 -> Keep 0, carry over 1
Discard the overflow bit.

We get 0100 = 4

Pretty neat!

The two’s complement also has the benefit of the sign-bit. But what’s more interesting about two’s complement is, if we look at the place-values it actually makes sense.

The LSB is in the 1s place, followed by the 2s and the 4s place, and the MSB looks like a sign-bit, but it's in fact the -8s place.
So,
1000 = -8.
And
-8 + 1 = -7 -> 1000 + 0001 = 1001
-8 + 4 = -4 -> 1000 + 0100 = 1100
-8 + 4 + 2 + 1 = -1 -> 1000 + 0100 + 0010 + 0001 = 1111

In Two’s Complement, the sign-bit is not just a representation, but it has a mathematical meaning, which is why our math works out.

So finally, let’s remember, to get a Two’s Complement, we have to first invert the binary number and add 1 to it.

In the next article, we will talk about the Logical Bitwise Operators.