7

Background

In two's complement arithmetics, if one wants to calculate a subtraction having only an adder that calculates

{cout,result}=full_adder(arg1,arg2,cin),

where cin and cout are incoming and outgoing carries, respectively, the way is to invert the second argument (a subtrahend) and to add extra one to the sum:

a-b = a + (~b) + 1

Using the full_adder() as defined above, that would be:

{some_cout,result}=full_adder(a,~b,1)

The some_cout is inverted borrow here: it is one when there were no borrow in ordinary subtraction of b from a and vice versa.

Next, that extra one could be actually an incoming borrow, which is also inverted: when it is one, a normal subtraction takes place, when it is zero, the result is 1 less:

{inv_borrowout,result}=full_adder(a,~b,inv_borrowin)

For those familiar with 6502 that is readily recognizable as the exact way the SBC instruction there works.

In more "conventional" architectures like 68000, Z80 or x86, the carries in subtraction are true borrows, that is, they get inverted before and after the addition with the inverted second argument. Extra inversion usually costs some logic, die space and worse timings.

Question

The one known member of 'inverted carries' architecture is 6502, the second known to me is ARM.

What CPU architecture was the first to optimize carries during subtraction by leaving them inverted? Were there any other adopters of such approach besides 6502 and ARM?

Improve this question
6
  • 3
    From recollection, the 6801 also has the inverted carry. I'd guess the 6502 inherited it from there, and the ARM inherited it from the 6502.
    – Lorraine
    Sep 24, 2021 at 14:28
  • 2
    I would expect that the first machines with carry propagation would have performed two's-complement subtraction by adding the ones' complement of the subtrahend along with an extra carry, and the inverting of the flag to represent "borrow" was a later innovation.
    – supercat
    Sep 24, 2021 at 15:58
  • Please use tags to define the scope of a question. Although you used 6502 and ARM as examples, they are unlikely to be the correct answer to the question ("Which was the first"), so they they do not belong as tags to the question.
    – DrSheldon
    Sep 24, 2021 at 16:04
  • 1
    Inverting is not free, but inverting a single bit is pretty cheap. In fact, modern designs often double invert in order to amplify for long wire runs.
    – Erik Eidt
    Sep 24, 2021 at 23:24
  • @OmarL I'm failing to confirm that 6801 has inverted carry. According to this bitsavers.org/components/motorola/6801/… its carry is not inverted.
    – lvd
    Sep 27, 2021 at 12:15

1 Answer 1

Reset to default
4

The PDP-8, like a number of other architectures, doesn't have subtraction.  Thus, subtraction is necessarily done by negation followed by addition.

The PDP-8 does have a carry bit (called the link bit).  On addition, a carry out of the high bit of accumulator will complement the link bit, so you have to set it to a known value to interpret it.  The negation operation is formed by one's complement of accumulator and increment in one instruction — and the link can be initialized to 0 or 1 in the same negation instruction, if desired.  The increment part will then complement the link if there's a carry out (which there will be for negative numbers, i.e. positive numbers complemented).

Improve this answer
5
  • 1
    You might also reference the PDP-5 which has a similar architecture, and came earlier. The PDP-4 represents a kind of transition between ones complement arithmetic and twos complement.
    – Walter Mitty
    Sep 26, 2021 at 12:01
  • 1
    I would question that L could be treated as carry here at all -- either inverted or not, complementing on true carryout or not. The reason is that it would be two different operations there, adding inverted subtrahend and then incrementing accumulator. Thus there's no meaningful carry for subtraction.
    – lvd
    Sep 28, 2021 at 16:40
  • 1
    @lvd, the negation operation (complementing & incrementing) on a PDP-8 would normally happen first, then second, addition (of negated operand) with the other operand. So, I suppose one could check the link bit after the negation to verify that didn't overflow, and then, proceed with addition, checking the link bit again afterwards.
    – Erik Eidt
    Mar 22, 2022 at 0:52
  • 2
    See this answer for the code for triple-precision C = A-B.
    – A. I. Breveleri
    Mar 30, 2022 at 22:25
  • 1
    No subtraction? The Manchester 'Baby' had only subtraction (no addition). Coupled with 'load accumulator negated', it got by.
    – another-dave
    Mar 30, 2022 at 22:52

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .