Why is it called "two's complement"?
Bernie Cosell
are called "one's complement" and "two's complement". What annoys me
about it is that once in a former lifetime, I really believe I _knew_
why they were called what they are [this on a machine that could do
both, and so much as now you have to be careful to do a floating-add,
long-add, integer-add, etc, back then we had to be careful to choose
between 'ADD' [1'scomp] and 'TAD' [2's comp]. But I cannot make _any_ sense
out of calling it 'two's complement' [one's complement is pretty straightfoward
--- see below]
/Bernie\
APPENDIX: What is one's complement and two's complement.
It occurs to me that some folk out there may not know what the hell I'm
asking about [and others might respond to my 'why is it called...'
inquiry with a 'how it works' followup]... so perhaps a small essay on
the whole mess might not be out of place:
The matter involves the representation of integers on binary computers,
and specifically the representation of negative integers. First, we
make an observation that some people miss: binary numbers don't quite
work, really: you are condemned to have an 'extra' one. That is, you
can represent 2^n numbers, and one is used up for 'zero'. So that
leaves you an odd number of representations left, which means that
_something_ is going to be a little wierd. Assuming that you start by
representing the same number of non-zero positive and negative integers
[since surely you'd like to be able to complement any representable
number, yes?], you end up with one representation left over. What
should it be? "NAN"? An extra zero? A number that is both positive
AND negative?
OK, now what is 1's comp and 2's comp? Well, there are a bunch of ways to
characterize the two representation systems. The simplest is:
Complementing a number: In 1's comp, you form the complement of a
number simply by complementing each bit. "-1" is simply FFF...FFE. In
2's comp, you form the complement of a number by taking the 1's
complement and adding one. And so "-1" is FFF...FFF. [...FFE + 1 =
...FFF]. Clearly 'one's complement' is named for this operation:
complementing each one. I don't see any obvious 2-ness in
complementing-and-adding-one, however.
Doing addition: In two's comp, addition is very easy: you simply add
bit-by-bit, right-to-left, propagating the carry as you go, and any
carry that drops off the left end is just thrown away [or passed up to
the next-higher term if you're doing multi-precision arithmetic]. In
one's comp things are a little more exciting: you do the normal
bit-by-bit right-to-left addition.. BUT.. if a carry propagates out of
the high-order bit you *feed*it*back* into the low-order bit. For
example: Adding 7 and -3: 7 = 0007; -3 = FFFC. Add them together in
the "normal" way, and you get 0003 plus a carry out the high end. Feed
the carry back in to get 0004. another amusing oddity: what about 5 +
-5? Well, -5 = FFFA. The 'first add' gets you FFFF with no carries at
all. Huh? why isn't A + -A *zero*?
Doing subtraction: In two's complement, doing "A - B" is pretty easy:
you just do a complement on the fly, and then use your same adder.
That is, the hardware does "A + (-B)". Well, for a ones complement
machine this would mean that you would NEVER get a real-zero as the
result of a simple "A - A" [you'd always get FFFF]. Instead, on
ones-complement machines, subtraction was done by "complement add
complement". You form 'A - B' not by complementing *B*, but by
complementing **A** (!): you complement (-A), add ((-A) + B), then
complement -((-A) + B). It is easy to see that this is algebraically
correct. What might not be so obvious is that this _never_ gets the
false-zero: it always gets a correct zero result.
The 'extra' representation: In one's complement, as the above
suggests, the 'extra' representation means "Minus zero". In two's
complement,the 'extra' representation is 8000. I often call it 'minus
infinity': it is more-negative thanthe complement of the largest
positive number [-7FFF = 8001] [and it is clearly a negative number,
isn't it? :-)]
Mark J Cromwell
I thought it was called 2's complement because you take 1's complement and
add 1 to it.
- Mark Cromwell
Jeff Kenton
> From time to time I wonder why the two most common arithmetic schemes
> are called "one's complement" and "two's complement".
>
The old mechanical calculators were ten's complement. For 2 and 10,
negative numbers are represented by subtracting the number from the
next higher power of 2 or 10 than the machine can represent. For
example, on a 32-bit machine, "-n" looks like "2^32 - n".
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
jeff kenton --- temporarily at jke...@pinocchio.encore.com
--- always at (617) 894-4508 ---
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
Jeremy J. Epstein
> [much stuff deleted]
>
> The 'extra' representation: In one's complement, as the above
> suggests, the 'extra' representation means "Minus zero". In two's
> complement,the 'extra' representation is 8000. I often call it 'minus
> infinity': it is more-negative thanthe complement of the largest
> positive number [-7FFF = 8001] [and it is clearly a negative number,
> isn't it? :-)]
On CDC mainframes (I used 7600s) you always tested for both zeroes.
FORTRAN being the lingua franca, you would see lines like
if (x .eq. 0 .or. x .eq. -0) goto 999
Strange to read until you figure it out...
--
Jeremy Epstein
TRW Systems Division
703-876-8776
jje%vir...@uunet.uu.net
M.R.Murphy
>In article <58...@bbn.BBN.COM>, cos...@bbn.com (Bernie Cosell) writes:
>> [much stuff deleted]
>
>On CDC mainframes (I used 7600s) you always tested for both zeroes.
>FORTRAN being the lingua franca, you would see lines like
> if (x .eq. 0 .or. x .eq. -0) goto 999
>Strange to read until you figure it out...
No, I don't believe it for a moment. All of us were scrupulous and always
wrote lines like
if (abs(x) .le. eps) goto 999
Didn't we always ? Didn't our implementations of algorithms work whether
on a 60-bit, 36-bit, or 32-bit with fewer bits for mantissa in normalized
floating point than any rational being would have expected? Didn't they?
:-)
--
Mike Murphy Sceard Systems, Inc. 544 South Pacific St. San Marcos, CA 92069
m...@Sceard.COM {hp-sdd,nosc,ucsd,uunet}!sceard!mrm +1 619 471 0655
David Vinayak Wallace
M.R.Murphy
[other stuff deleted 'cause noone probably cares :-)]
>[I hope I got those attributions correct. :-)]
Looked scrupulous to me.
>
>I thought this was obvious, BUT since no one has posted it yet...
>
>If x is a REAL number, one would code as in the latter example. But,
>since we're talking about two's complements, I'd assume that we should
>be discussing INTEGER variables. (Where's your INTEGER X?)
>
>In the case of x being INTEGER, I can definitely see checking for both
>"zeros."
There are two's complement floating point representations, one's complement
floating point representations, decimal floating point representations,
umpteen different schemes for the representation of characteristic/mantissa,
and who-knows-how-many ad hoc programs for the conversion of one to another.
In one's complement floating point representations, 0.0 and -0.0 may both
be valid floating point numbers. My recollection is that if(x.eq.0.0) would
branch on x containing 0.0 or -0.0 using the compilers on the one's complement
machines on which I worked so long ago. Howsomever, to trust x.eq.0.0 is
risky if one actually wants to depend on the numbers produced by a program.
Better to use the epsilon style test. Also a bad idea to trust results from
calculations like x=(a+b)/(c-d). How many folks just code away without
considering the consequences? Or without checking if
IF(IABS(I).EQ.0)GOTO 999
IF(I.EQ.0.OR.I.EQ.-0)GOTO 999
or
IF(I)998,999,998
998 CONTINUE
produces better code in a particular environment. This is getting afield from
folklore, sorry.
Some folklore related to the above. About 20 years ago, I put together a
time-sharing system based on a single-console process control system. Serving
users isn't that different from closing valves in a timely fashion. The
manufacturer of the system wanted to convince a potential customer to replace
a rather large number crunching mainframe (one's complement :-) with the much
less expensive mini-computer system.
The customer said, "Maybe, maybe, but you have to run this test suite and
show us the output is the same." We converted 14 of the 16 programs in
the suite in one day, mostly by changing the A10 format specifiers and the
associated read and write statments, and by changing two-way arithmetic if
statements to less vendor specific form, and the customer was suitably
impressed. Two of the programs wouldn't produce the same output, no matter how
we diddled. It turned out that the programs used ill-conditioned algorithms
and were actually producing junk output on the mainframe. Judicious write
statements found the problems to be of the (a+b)/(c-d) variety, coupled with
a few uninitialized variables. We fixed the programs on the mini-computer
system, showed the customer's representatives, and then watched them scramble
to call home. Seemed that they were trusting the numbers that their production
system was crunching.
A clear demonstration of the advantages of a small, interactive system with
rapid turnaround, even if the terminals were KSR33's :-) They ended up buying.
Dik T. Winter
> FORTRAN being the lingua franca, you would see lines like
> if (x .eq. 0 .or. x .eq. -0) goto 999
> Strange to read until you figure it out...
Strange, I cannot figure it out. Considering that the ZR isntruction would
branch on both +0 and -0 and that X-(+0) would result in +0 whether X was
+0 and -0. On the other hand:
if (x .ge. 0)
might be mishandled by the compiler to branch on positive numbers only
(i.e. not on -0). But the cases where standard arithmetic would result
in -0 without any -0 input are extremely rare (INT(-0.1) is a
possible candidate, offhand I know no others).
--
dik t. winter, cwi, amsterdam, nederland
d...@cwi.nl
Richard Bielak
;-)
...richie (sorry, couldn't resist)
--
+----------------------------------------------------------------------------+
|| Richie Bielak (212)-815-3072 | If a thousand people say a foolish |
|| USENET: ric...@bony.com | thing, it's still a foolish thing. |
+----------------------------------------------------------------------------+