Why Two's Complement?

I'm writing a tutorial to teach kids (ages 9 to 13) about programming. I started with computers themselves, they don't have that much to do with computer science, it's more about the process involved with a solution to a computational problem.

With that starting point, I'm guid开发者_运维知识库ing them toward an understanding that machines can help us with certain computational problems. People are great at abstract thinking and imagination, but computers are AWESOME at following a well-specified routine. They can do it again and again, at amazing speed!

Representing numbers in binary format has already been covered in my tutorial. But how do you represent negative numbers? There are so many ways to do this, in any notational system, but the system chosen for computers is for a very specific reason: to reduce the amount of machinery involved with adding signed integer values. We don't want to have to construct and build separate chips just to handle negative numbers, we want to use the same chips we have been using for natural number arithmetic!

If someone asked you on the street (as totally unrealistic as this seems) "how do computers represent negative numbers, and why do they represent them this way?"

My specific questions:

1. How do computers represent negative numbers?

2. Why do computers represent negative numbers this way?

I would guess that this many experienced developers would have to think about this a bit. Some might not even be able to come up with an answer. I'm not trying to be pompous, this is from actual experience, I've asked professional developers this question and they can't answer it. They draw a blank stare. Give them JBoss and JavaBeans and they will steamroll you with confidence. So funny! I too struggle with this question, I have to remind myself of the answers every time and I need a piece of paper or white board to work out a solution. What I'm hoping is to guide students toward a better understanding of the machine they are working with.

---

1.How do computers represent negative numbers?

Take the positive value, invert all bits and add one.

2.Why do computers represent negative numbers this way?

It makes easy to add 7 in -7 and came up with a zero. The bit operations are fast.

---

How does it make it easy?

Take the 7 and -7 example. If you represent 7 as 00000111, to find -7 invert all bits and add one:

11111000 -> 11111001

Now you can add following standard math rules:

  00000111
+ 11111001
-----------
  00000000

For the computer this operation is relatively easy, as it involves basically comparing bit by bit and carrying one.

If instead you represented -7 as 10000111, this won't make sense:

  00000111
+ 10000111
-----------
  10001110 (-14)

To add them, you will involve more complex rules like analyzing the first bit, and transforming the values.

And don't forget what @trashgod said, in 2's complement you have only one zero. To check it:

00000000
11111111 (invert all bits)
00000000 (add one)

Differently from 00000000 (0) being equal to 10000000 (-0)

---

Why do computers represent negative numbers this way?

Two big reasons I can think of:

• Simplicity of basic arithmetic operations. You don't have to worry about inspecting the sign bit to decide whether to add or subtract.
• Uniqueness of representation. It's nice to not have to worry about negative zero since there is no way to represent negative zero in two's complement.

From Wikipedia:

The two's-complement system has the advantage of not requiring that the addition and subtraction circuitry examine the signs of the operands to determine whether to add or subtract. This property makes the system both simpler to implement and capable of easily handling higher precision arithmetic. Also, zero has only a single representation, obviating the subtleties associated with negative zero, which exists in ones'-complement systems.

---

How do computers represent negative numbers?

Computers represent negative numbers by calculating the result that you would get if you subtracted that number from zero, using their normal rules for subtraction. That is, to find what -5 looks like in binary, you subtract 5 (in binary) from 0 (in binary):

0  0  0  0 -
0  1  0  1
----------

              (borrow)
-> 1 -> 1 -> 1 ->10 -
   0    1    0    1
   ----------------
   1    0    1    1

..so -5 looks like 1011 in binary.

Why do computers represent negative numbers this way?

Because doing it this way means that when the computer is adding and subtracting numbers, it doesn't have to check if some of them are negative or not: the maths works out anyway. This makes the computer simpler, and simpler computers are cheaper to build.

---

Write down a number line

-32768... -1, 0, 1, 2, ... 32767

Add moves to the right. Subtract moves to the left. Conceptually nice, but how can we represent the sign?

We can use "signed magnitude" where the sign and the value are separate. This gets confusing because we have two parallel number lines with differing signs.

An alternative to "signed magnitude" is to encode each number as another number.

We can add an offset of 32768 to all the numbers. The new range is the unsigned 0 to 65535. Everything still works, right? You just have a fixed bias value applied to all the numbers. Add moves to the right. Subtract moves to the left. 32768 can be decoded to 0. 0 can be decoded to -32768.

This works perfectly. The "encoding" a number is simply adding a bias. "Decoding" a number simply subtracts the bias.

Here's another encoding scheme.

Carry all the negative numbers over to the other side of the number line.

0, 1, 2, ..., 32767, -32768, ... -1

Addition still moves to the right. Take any number (with one exception). The number to the right of it is always larger.

The one exception is 32767. The number to the right of it is "overflow".

Subtract still moves to the left. Take any number (with one exception). The number to the left is always smaller. The one exception is -32768. The number on the left of it is "underflow".

The encoding and decoding are a little more involved. 0 to 32767 have a trivial encoding and decoding: do nothing. The numbers are encoded as themselves. 32768 to 65535, however, are encodings of negative numbers.

---

Two's compliment is used to simplify addition and subtraction into one operation which can be performed by one hardware unit. Instead of subtracting one number from another, in two's compliment arithmetic you add one number's inverse to another. Back in the olden days, having a separate piece of hardware for subtracting numbers would have been a pretty big deal, so coming up with a system to perform subtraction and addition with a single unit was very useful.

You can find the inverse of any number in two's compliment by flipping the bits and adding one. For instance, -1 would be represented as follows in a four bit implementation:

 1: 0001
-1: 1110 + 1 = 1111

You can verify this by adding the two:

 0001 + 1111 = 10000

We're working with four bits, however, so the result is truncated. We now have 0000, or 0. We have added a number and its negative and gotten zero. Hurray!

Now, for one final example, let's do 4 - 6. 4 is represented as 0100. 6 is represented as 0110. To get -6, flip the bits and add one: 1001 + 1 = 1010. 0100 + 1010 = 1110. 1110 is a negative number (all numbers with a 1 in the most significant digit are negative in two's compliment). To find out its absolute value, we flip the bits and add 1. 0001 + 1 = 0010, or 2. Therefore, the result of our addition is -2. 4 - 6 -2. Our math checks out.

Congratulations. You are now exactly as smart as a computer.

---

Q1. How do computers represent negative numbers?

2's compliment method!

Q2 . Why do computers represent negative numbers this way?

Here's how 2's compliment work:

For any x,

x + ~x   = all the bits set  
x + ~x   = 2^m - 1      (2^m = the range of numbers we opt)  
  -x     = ~x + 1 - 2^m (we can cancel out mod 2^m, which gives)  
  -x     = ~x + 1 

As you can see, 2's compliment is logical and easy to implement and doesn't have corner cases and that is why it is preferred over other methods.
Lets consider 1's compliment , a method with corner cases I was talking about, in which 0 and -0 exist (all bits not set = 0, all bits set = -0) which translates to more operations to perform for the Hardware circuits, especially during operations with a number x and -0. [Wikipedia has nice examples on Avoiding Negative Zero, you can have a look at them]

I hope this explanation soothes the minds of your kids...