Negative Value Integers are more interesting than you think

I assume most of you know there is one bit in the binary representation of a signed integer indicating, well, its sign. But did you ever go deeper? Just hearing "The biggest number a signed integer can represent is only half of the biggest number an unsigned integer can represent, due to one bit being used to indicate the sign" may lead you to think that's it. You just change the leftmost/most significant bit to get a positive or negative number. That's usually not the case with modern systems though and I think its really cool how its actually done.

Info

In the following article I will only address the common basics. Handling overflows for example is language specific and unrelated to the underlying idea. For simplicity I will use only 4 bits and addition.

What is wrong with just flipping a bit?

Per se, nothing. But there are better ways.

What is 0?

0000 of course, stupid question you might say. And you wouldn't be wrong.

But what about 1000? If we just use the leftmost bit to indicate the sign, we get 0 and, surprise, -0. Not a great start.

What about addition/subtraction?

Let's try 4+(-2) = 2.

sign | absolute value
0    | 100 // 4
1    | 010 // -2

We are adding binary integers by writing a 0 in the result when there is an even amount of 1s at a position (including the carry) and a one if its uneven. We carry if there are at least two 1s at the position. We start at the least significant bit. Let's apply it:

Step 1

Step 2

Step 3

Step 4

Ok, now we got 1110. That's, wait, -6? That can't be right?

It should've been 2!

Why does it happen?

The hardware treated 1010 as the unsigned value 10 instead of -2, so we calculated 4+10 = 14, which in our 4-bit system becomes 1110 (-6 in sign-magnitude).

How do we fix this?

Hmm, we could determine whether to use addition or subtraction based on their sign, but no, that wouldn't work either, it would break the sign bit when adding two negative values... Maybe dedicated hardware for signed additions? But that's inefficient... Or - what if we encode negative values so they naturally work with unsigned addition? Let me introduce you to:

Two's Complement

Two's Complement is a smart way to format signed integers. It entirely eliminates the need for the hardware to know whether it handles a signed or unsigned integer and whether its positive or negative. It just works with the same logic unsigned integers use. Subtraction just becomes addition of the Two's Complement!

Here is how

Like before, we indicate the sign with the leftmost bit. But the conversion from positive to negative is slightly different. Let's try it on -2.

Step 1: Invert

0010 -> 1101

Step 2: Add 1

1101 -> 1110

Step 2 eliminates the problem of having +0 and -0. Eliminating -0 leads to the negative space being 1 larger than the positive one. 4-bit signed integers using Two's Complement therefore range from -8 (1000) to +7 (0111)

Addition

Let's try 4+(-2) = 2 again:

Step 1

Step 2

Step 3

0100
 v
1110
 =
1010
1 (carry)

Step 4

0100
v
1010
1
 =
 0010
1 (carry)

We ignore the overflowing carry, so our result now is 0010, which is 2 in decimal, like it's supposed to be! It works with two negative integers too:

-2+(-3) = -5

-2 = 1110

-3 = 1101

Step 1

Step 2

Step 3

1110
 v
1111
 =
1011
1 (carry)

Step 4

1110
v
1011
1
 =
 1011
1 (carry)

Again, we ignore the overflowing carry, so 1011 is our result. We can check it's correct by deriving -5's bit representation from 5:

Step 1: Invert

0101 -> 1010

Step 2: Add 1

1010 -> 1011

Voilà, we are correct!

Conclusion

Two's complement lets us use the same addition circuitry for both signed and unsigned integers, eliminating the need for special hardware.

Notes

While it's not that important to know using modern, pretty abstracted, languages, I just found it really cool when I learned about it a few days ago. It's an interesting detail you rarely think about. I hope you learned something new and had fun reading.

Until next time, Mia