Twos Complement Notation

Date: 12/17/2001 at 09:42:16
From: Klaartje van Riemsdijk
Subject: Sign byte

I'm learning to make computer programs. I'm a fourth-generation 
programmer so I have not learned enough about bits and bytes. Could 
you answer the question how to make a 2-byte negative and at which 
place in the 16 bits the sign bit is placed and why there?

Date: 12/17/2001 at 11:26:21
From: Doctor Tom
Subject: Re: Sign byte

Hello Klaartje,

There are different ways to do it, depending on the architecture of 
the machine, but nowadays, almost every computer does it the same way, 
and it's called "two's complement."  Here's the idea:

We just pretend that we are looking at the bottom bits of an 
infinitely long number, so the number you write for decimal 5 is:

101 binary, or

   00000000 00000101  in 16 bits

or

   ...0000000000000000000000000000000000000101

in your imagination.

All the positive numbers and zero have an infinite set of zeroes to 
the left. So to get -1, for example, just start with the infinite set 
of zeros (representing zero) and subtract 1. You have to keep carrying 
forever, but you eventually get:

   ...1111111111111111111111111111111111111111

or, in 16 bits, you represent -1 as:

11111111 11111111

You can do any negative number this way, to obtain:

   -2 = 11111111 11111110
   -3 = 11111111 11111101
   -4 = 11111111 11111100

and so on.

The most negative number that can be represented in 16 bits is:

   -32768 = 10000000 00000000

The most positive number is:

   32767 = 01111111 11111111

The highest order bit is 1 if the number is negative and zero if it's 
positive.

Addition and subtraction are trivial - just do the addition all the 
way to the end. The hardware actually examines the carry bit out of 
the high-order position to see if overflow occurred, et cetera.

There is a very easy way to find the representation of a negative 
number if you have the representation of the positive version. For 
example, if you know that 11 (decimal) is:

   00000000 00001011

then to find -11, change all the bits:

   11111111 11110100

and add 1:

   11111111 11110101

It's easy to check that this is correct, since a positive and negative 
version of a number should add to zero. The positive and negative 
versions will have different bits in all the positions if we ignore 
the 1 that we added. Here's an example.

Positive:

   00101101 11011100

Negative:

    11010010 00100011
   +00000000 00000001

Add all three together. The sum of the first two is always:

   11111111 11111111

and if we add 1, the carries go to infinity, making all zeroes.

If you want details, look for a book on "computer arithmetic" and look 
up "two's complement notation" or "2s complement notation."

- Doctor Tom, The Math Forum
  http://mathforum.org/dr.math/