[Verba] Two's complement

[Stuart D. Gathman]

On Sun, 29 Jan 2006, Stuart D. Gathman wrote:

> >>> ~5
> -6
> >>> ~1
> -2
> >>> ~2
> -3
> 
> Whoa!  Negative numbers?  Integers in python are treated as infinite bit
> sequences.  When all the bits to the "left" (more significant) of the
> interesting bits are 0 to infinity, then the number is positive (or zero).
> When all the bits to the left of the interesting bits are 1, then the 
> number is negative.  So for instance ~0 == -1, because the NOT reverses
> all the bits out to infinity.  (Of course, the computer doesn't *really*
> store infinite bits.  It just treats the most significant bit stored as
> if it extended to infinity.)

You will still be surprised by the results of the NOT operator, until we
have explained "two's complement".  Suppose you have a 4 digit decimal
calculator with no sign.  You could represent negative numbers as
10000 - number.  For instance, -1 would be 9999, -2 would be 9998, etc.

Addition works out just the way it should (assuming the calculator discards
digits beyond 4).  For instance, 2 - 3 is 2 + -3 which is 2 + 9997, or 9999
which is -1.  This is called "ten's complement".  Binary computers use a
similar system base 2.  (Actually, older binary computers used a "one's
complement" system where negative numbers had all bits reversed from the
positive number.)  If you have 8 bit bytes, then -1 is 11111111.
Python integers use two's complement arithmetic with an "infinite" word size.
For instance, in infinite ten's complement, -2 would be ...999998, where
there are an infinite number of 9s to the left.  Similarly, -2 in
infinite two's complement is ...111110, where there are an infinite number
of 1s to the left.

-- 
	      Stuart D. Gathman <stuart at bmsi.com>
Business Management Systems Inc.  Phone: 703 591-0911 Fax: 703 591-6154
"Confutatis maledictis, flamis acribus addictis" - background song for
a Microsoft sponsored "Where do you want to go from here?" commercial.