Groups > comp.lang.c > #72019

Re: Ones' complement subtraction

From	glen herrmannsfeldt <gah@ugcs.caltech.edu>
Newsgroups	comp.lang.c
Subject	Re: Ones' complement subtraction
Date	2015-10-06 02:14 +0000
Organization	Aioe.org NNTP Server
Message-ID	<muvapf$f9k$1@speranza.aioe.org> (permalink)
References	(7 earlier) <muthba$83c$1@speranza.aioe.org> <lntwq53zw4.fsf@kst-u.example.com> <a6fd81a8-4754-4a20-be95-ce17f23738b9@googlegroups.com> <muurpq$ium$1@speranza.aioe.org> <2fc3b397-e0d9-41b5-87aa-c7cee16816c4@googlegroups.com>

Show all headers | View raw

supercat@casperkitty.com wrote:

(snip, I wrote)
>> The other way never generates ~0 unless an operand of an arithmetic
>> operation is ~0. If you use a ones complement subtractor, and
>> do addition by subtracting the complement, this is the natural
>> result.

> Do ones'-complement subtractors start by doing a magnitude 
> comparison between the two values, swapping them if needed, 
> then performing the subtraction and negating the result if 
> required, or is there an easier way?  

You can make a ones complement adder taking the carry out of
the MSB and using it as the carry in for the LSB. Next, you
usually add carry lookahead logic, which I think works just
fine in that case. When the result isn't zero, that should
work as well as twos complement adders. 

When the result is zero, there is a theoretical possibility
that it won't converge.  That is, that it won't converge
to either 0 or ~0. As far as I know, this isn't a problem
in real adders, but it does complicate the timing calculation.

> Two's-complement subtraction allows the bits to be computed 
> LSB in order first with no bit being dependent upon any 
> higher bits, but ones'-complement subtraction would not 
> allow that.  If the low-order bytes of X and Y are 0x80 and 
> 0x01, the low-order byte of X-Y might be 0x7F or 0x80, 
> and figuring out which would require processing all 
> higher-order bytes.

Both the adder and subtractor can be done in parallel with
the MSB carry out going to the LSB carry in. If the sum isn't
zero, then either the least or most significant byte doesn't
depend on the other. 

For an adder, ~0+0 and 0+~0 both give ~0 as a sum. 
Actually, ~x+x and x+~x do for all x.

With an appropriate subtractor, x-x gives 0 for all x, except ~0.

> I could see some benefit to a ones'-complement floating-point format (in
> which case the sign bit is extended infinitely far on *both* sides of the
> number) because floating-point requires special handling of add/subtract
> operations that cross zero, but for integers it seems like ones'-complement
> would add extra complexity and I can't see any benefit.

I never heard why Cray liked ones complement through the CDC years.

With the Cray-1 he finally decided on twos complement.

-- glen

-- glen

Thread

Re: Reading beyond the end of file Tim Rentsch <txr@alumni.caltech.edu> - 2015-09-11 10:06 -0700
  Re: Reading beyond the end of file Geoff <geoff@invalid.invalid> - 2015-09-11 12:41 -0700
    Re: Reading beyond the end of file Tim Rentsch <txr@alumni.caltech.edu> - 2015-09-26 14:24 -0700
      Re: Reading beyond the end of file Geoff <geoff@invalid.invalid> - 2015-09-26 21:49 -0700
        Re: Reading beyond the end of file Tim Rentsch <txr@alumni.caltech.edu> - 2015-10-01 13:57 -0700
          Re: Reading beyond the end of file Geoff <geoff@invalid.invalid> - 2015-10-01 17:22 -0700
            Re: Reading beyond the end of file raltbos@xs4all.nl (Richard Bos) - 2015-10-02 13:05 +0000
            Re: Reading beyond the end of file Tim Rentsch <txr@alumni.caltech.edu> - 2015-10-04 17:56 -0700
  Re: Reading beyond the end of file Joe Pfeiffer <pfeiffer@cs.nmsu.edu> - 2015-09-11 13:55 -0600
    Re: Reading beyond the end of file Tim Rentsch <txr@alumni.caltech.edu> - 2015-09-26 14:14 -0700
      Re: Reading beyond the end of file Siri Cruz <chine.bleu@yahoo.com> - 2015-09-26 14:43 -0700
        Re: Reading beyond the end of file Lew Pitcher <lew.pitcher@digitalfreehold.ca> - 2015-09-26 17:57 -0400
        Re: Reading beyond the end of file Tim Rentsch <txr@alumni.caltech.edu> - 2015-10-01 14:01 -0700
      Re: Reading beyond the end of file Joe Pfeiffer <pfeiffer@cs.nmsu.edu> - 2015-09-26 22:18 -0600
        Re: Reading beyond the end of file Tim Rentsch <txr@alumni.caltech.edu> - 2015-10-01 12:58 -0700
          Re: Reading beyond the end of file Joe Pfeiffer <pfeiffer@cs.nmsu.edu> - 2015-10-01 15:08 -0600
            Re: Reading beyond the end of file Tim Rentsch <txr@alumni.caltech.edu> - 2015-10-04 18:03 -0700
              Re: Reading beyond the end of file glen herrmannsfeldt <gah@ugcs.caltech.edu> - 2015-10-05 04:02 +0000
      Re: Reading beyond the end of file raltbos@xs4all.nl (Richard Bos) - 2015-10-02 13:11 +0000
        Re: Reading beyond the end of file supercat@casperkitty.com - 2015-10-02 09:31 -0700
          Re: Reading beyond the end of file Richard Damon <Richard@Damon-Family.org> - 2015-10-03 16:07 -0400
        Re: Reading beyond the end of file Tim Rentsch <txr@alumni.caltech.edu> - 2015-10-04 19:06 -0700
  Re: Reading beyond the end of file Keith Thompson <kst-u@mib.org> - 2015-09-11 14:36 -0700
    Re: Reading beyond the end of file Tim Rentsch <txr@alumni.caltech.edu> - 2015-09-26 14:05 -0700
      Re: Reading beyond the end of file Keith Thompson <kst-u@mib.org> - 2015-09-26 18:53 -0700
        Re: Reading beyond the end of file Tim Rentsch <txr@alumni.caltech.edu> - 2015-10-01 13:49 -0700
          Re: Reading beyond the end of file Richard Damon <Richard@Damon-Family.org> - 2015-10-01 20:23 -0400
            Re: Reading beyond the end of file glen herrmannsfeldt <gah@ugcs.caltech.edu> - 2015-10-02 06:14 +0000
            Re: Reading beyond the end of file Tim Rentsch <txr@alumni.caltech.edu> - 2015-10-04 19:03 -0700
              Re: Reading beyond the end of file Richard Damon <Richard@Damon-Family.org> - 2015-10-04 22:55 -0400
                Re: Reading beyond the end of file glen herrmannsfeldt <gah@ugcs.caltech.edu> - 2015-10-05 04:27 +0000
                Re: Reading beyond the end of file Keith Thompson <kst-u@mib.org> - 2015-10-04 22:21 -0700
                Re: Reading beyond the end of file glen herrmannsfeldt <gah@ugcs.caltech.edu> - 2015-10-05 09:53 +0000
                Re: Reading beyond the end of file James Kuyper <jameskuyper@verizon.net> - 2015-10-05 13:15 -0400
                Re: Reading beyond the end of file supercat@casperkitty.com - 2015-10-05 10:25 -0700
                Re: Reading beyond the end of file glen herrmannsfeldt <gah@ugcs.caltech.edu> - 2015-10-05 21:30 +0000
                Re: Reading beyond the end of file glen herrmannsfeldt <gah@ugcs.caltech.edu> - 2015-10-05 21:27 +0000
                Re: Reading beyond the end of file supercat@casperkitty.com - 2015-10-05 10:17 -0700
                Re: Reading beyond the end of file Keith Thompson <kst-u@mib.org> - 2015-10-05 11:59 -0700
                Re: Reading beyond the end of file supercat@casperkitty.com - 2015-10-05 13:44 -0700
                Re: Reading beyond the end of file glen herrmannsfeldt <gah@ugcs.caltech.edu> - 2015-10-05 21:58 +0000
                Ones' complement subtraction supercat@casperkitty.com - 2015-10-05 15:28 -0700
                Re: Ones' complement subtraction glen herrmannsfeldt <gah@ugcs.caltech.edu> - 2015-10-06 02:14 +0000
                Re: Ones' complement subtraction supercat@casperkitty.com - 2015-10-06 08:48 -0700
                Re: Ones' complement subtraction glen herrmannsfeldt <gah@ugcs.caltech.edu> - 2015-10-06 20:55 +0000
                Re: Ones' complement subtraction supercat@casperkitty.com - 2015-10-06 14:41 -0700
                Re: Ones' complement subtraction glen herrmannsfeldt <gah@ugcs.caltech.edu> - 2015-10-07 00:14 +0000
                Re: Reading beyond the end of file Keith Thompson <kst-u@mib.org> - 2015-10-05 15:24 -0700
                Re: Reading beyond the end of file glen herrmannsfeldt <gah@ugcs.caltech.edu> - 2015-10-05 21:39 +0000
                Re: Reading beyond the end of file Keith Thompson <kst-u@mib.org> - 2015-10-05 15:31 -0700
                Re: Reading beyond the end of file glen herrmannsfeldt <gah@ugcs.caltech.edu> - 2015-10-06 03:04 +0000
                Re: Reading beyond the end of file Keith Thompson <kst-u@mib.org> - 2015-10-06 08:55 -0700
                Re: Reading beyond the end of file supercat@casperkitty.com - 2015-10-06 11:44 -0700
                Re: Reading beyond the end of file Richard Damon <Richard@Damon-Family.org> - 2015-10-05 23:16 -0400
                Re: Reading beyond the end of file James Kuyper <jameskuyper@verizon.net> - 2015-10-06 10:29 -0400
                Re: Reading beyond the end of file Keith Thompson <kst-u@mib.org> - 2015-10-06 08:56 -0700
                Re: Reading beyond the end of file Richard Damon <Richard@Damon-Family.org> - 2015-10-06 23:13 -0400
                Re: Reading beyond the end of file supercat@casperkitty.com - 2015-10-06 22:01 -0700
                Re: Reading beyond the end of file Keith Thompson <kst-u@mib.org> - 2015-10-07 08:43 -0700
                Re: Reading beyond the end of file supercat@casperkitty.com - 2015-10-07 10:02 -0700
                Re: Reading beyond the end of file Keith Thompson <kst-u@mib.org> - 2015-10-07 13:08 -0700
                Re: Reading beyond the end of file Richard Damon <Richard@Damon-Family.org> - 2015-10-07 22:03 -0400
                Re: Reading beyond the end of file Tim Rentsch <txr@alumni.caltech.edu> - 2015-10-05 01:47 -0700

csiph-web