implementation of unsigned addition on one's complement machines

[Luca Forlizzi]

Hello,
this is my first post in this group so I would like to greet
everyone.
I have a question about one's complement arithmetic, and it has been
suggested to me that since comp.arch.arithmetic is dead, this might be
the right place to ask.

In 2's complement, the same add/sub hardware instruction compute the
correct result for both signed and unsigned addition (although on
MIPS, for instance, there are separate instructions so that signed add
can generate overflow).
How unsigned addition is implemented in one's complement CPUs? the
instrucitons performing add in one's complement do not produce the
correct result for unsigned addition. Do such CPUs have distinct add
instructions for signed and unsigned operands?


Luca Forlizzi

[Torben �gidius Mogensen]

Luca Forlizzi <luca.f...@gmail.com> writes:


> How unsigned addition is implemented in one's complement CPUs?

I can't find unsigned addition in the Univac 1100 instruction set (which
uses one's complement as default and supports sign+magnitude as well).

So I suspect the answer is "It isn't".

Torben

[Torben Ægidius Mogensen]

However, if you don't overflow, ones-complement addition works fine for
unsigned addition. The difference between ones-complement addition and
unsigned addition is that, if the addition has a carry out, this is
added back in to the lsb. So if this never happens, you are O.K.

Torben

[Luca Forlizzi]

On 15 Nov, 10:29, torb...@diku.dk (Torben Ægidius Mogensen) wrote:
> torb...@diku.dk (Torben Ægidius Mogensen) writes:

>
> > Luca Forlizzi <luca.forli...@gmail.com> writes:
>
> >> How unsigned addition is implemented in one's complement CPUs?
>
> > I can't find unsigned addition in the Univac 1100 instruction set (which
> > uses one's complement as default and supports sign+magnitude as well).
>
> > So I suspect the answer is "It isn't".
>
> However, if you don't overflow, ones-complement addition works fine for
> unsigned addition.  The difference between ones-complement addition and
> unsigned addition is that, if the addition has a carry out, this is
> added back in to the lsb.  So if this never happens, you are O.K.
>
>         Torben

you are right, thanks for pointing it out. This indeed solve the
problem in some cases. However not in the case I have in mind, i.e.,
how to implement C language unsigned arithmetic in one's complement
CPUs.
As you probably know, in C unsigned arithmetic is modular. This is
easily implemented in two's complement by ignoring the carry out of
addition.
So, either a one's complement CPU also has an add instruction that
does not add back the carry out, or the unsigned add operation has to
be implemented by a sequence of operation. In the latter case, I would
expect signed arithmetic in C to be faster than the unsigned one.

[nm...@cam.ac.uk]

In article <49f2f40a-cf50-4f49...@cc2g2000vbb.googlegroups.com>,

Luca Forlizzi <luca.f...@gmail.com> wrote:
>
>As you probably know, in C unsigned arithmetic is modular. This is
>easily implemented in two's complement by ignoring the carry out of
>addition.

Division and remainder aren't.


Regards,
Nick Maclaren.

[Luca Forlizzi]

On 15 Nov, 11:28, n...@cam.ac.uk wrote:
> In article <49f2f40a-cf50-4f49-89ee-4d4e9ad56...@cc2g2000vbb.googlegroups.com>,

> Luca Forlizzi  <luca.forli...@gmail.com> wrote:
>
>
>
> >As you probably know, in C unsigned arithmetic is modular. This is
> >easily implemented in two's complement by ignoring the carry out of
> >addition.
>
> Division and remainder aren't.

excuse me, do you mean that they are not modular or that the can not
be
implemented by ignoring the carry out?

I would believe you in the latter case.
In the former, it seems to me that section 6.2.5 par.9 of the C
standard refers to all
operations. But since I know you as a regular on clc, it is well
possible that you know something more than me, in which case I ask you
to explain why 6.2.5 does not apply.

Luca

[Luca Forlizzi]

On 14 Nov, 17:55, torb...@diku.dk (Torben gidius Mogensen) wrote:

I have done a quick research using wikipaedia, also the PDP1, CDC6600
and CDC 160 are one's complement machines and seem not to have add
instructions for unsigned numbers.
This confirms your suspect. Thanks a lot

[nm...@cam.ac.uk]

In article <8503c9bb-07c6-4bae...@g21g2000yqc.googlegroups.com>,

Luca Forlizzi <luca.f...@gmail.com> wrote:
>>
>> >As you probably know, in C unsigned arithmetic is modular. This is
>> >easily implemented in two's complement by ignoring the carry out of
>> >addition.
>>
>> Division and remainder aren't.
>
>excuse me, do you mean that they are not modular or that the can not
>be implemented by ignoring the carry out?

There is no carry-out involved except, debatably, when dividing
-(1+maxint) by -1 on a two's complete system. They aren't modular,
and that occasionally causes trouble.


Regards,
Nick Maclaren.

[Anton Ertl]

Luca Forlizzi <luca.f...@gmail.com> writes:
>How unsigned addition is implemented in one's complement CPUs? the
>instrucitons performing add in one's complement do not produce the
>correct result for unsigned addition. Do such CPUs have distinct add
>instructions for signed and unsigned operands?

If they want to use all the bits for unsigned numbers, then a separate
unsigned addition (and subtraction) is needed. However, you can
define the positive subset of the signed integers supported by the
machine to be the unsigned numbers; then you can use the ordinary
(signed) addition for these "unsigned" numbers; but you don't get
wrap-around on overflows then.

I wonder how C's guaranteed wraparound on unsigned overflow is
implemented on such machines.

- anton
--
M. Anton Ertl Some things have to be seen to be believed
an...@mips.complang.tuwien.ac.at Most things have to be believed to be seen
http://www.complang.tuwien.ac.at/anton/home.html

[Anton Ertl]

nm...@cam.ac.uk writes:
>In article <8503c9bb-07c6-4bae...@g21g2000yqc.googlegroups.com>,
>Luca Forlizzi <luca.f...@gmail.com> wrote:
>>>
>>> >As you probably know, in C unsigned arithmetic is modular. This is
>>> >easily implemented in two's complement by ignoring the carry out of
>>> >addition.
>>>
>>> Division and remainder aren't.
>>
>>excuse me, do you mean that they are not modular or that the can not
>>be implemented by ignoring the carry out?
>
>There is no carry-out involved except, debatably, when dividing
>-(1+maxint) by -1 on a two's complete system.

That's not a division of unsigned numbers. I don't think you can
produce an overflow with division (or remainder) of unsigned numbers
in C, so your mentioning of division does not contribute anything but
noise to the discussion. Btw, wouldn't a C standards bigot write
(-maxint)-1 instead of -(1+maxint)?

[nm...@cam.ac.uk]

In article <2011Nov1...@mips.complang.tuwien.ac.at>,

Anton Ertl <an...@mips.complang.tuwien.ac.at> wrote:
>>>>
>>>> >As you probably know, in C unsigned arithmetic is modular. This is
>>>> >easily implemented in two's complement by ignoring the carry out of
>>>> >addition.
>>>>
>>>> Division and remainder aren't.
>>>
>>>excuse me, do you mean that they are not modular or that the can not
>>>be implemented by ignoring the carry out?
>>
>>There is no carry-out involved except, debatably, when dividing
>>-(1+maxint) by -1 on a two's complete system.
>
>That's not a division of unsigned numbers. I don't think you can
>produce an overflow with division (or remainder) of unsigned numbers
>in C, so your mentioning of division does not contribute anything but
>noise to the discussion. Btw, wouldn't a C standards bigot write
>(-maxint)-1 instead of -(1+maxint)?

Curious. You are usually both reasonably polite and reasonably
clueful but, in that post, you are neither.

Consider 3-bit unsigned integers, for simplicity. 7/5 = 3 in
true modular arithmetic.


Regards,
Nick Maclaren.

[Terje Mathisen]

Anton Ertl wrote:
> If they want to use all the bits for unsigned numbers, then a separate
> unsigned addition (and subtraction) is needed. However, you can
> define the positive subset of the signed integers supported by the
> machine to be the unsigned numbers; then you can use the ordinary
> (signed) addition for these "unsigned" numbers; but you don't get
> wrap-around on overflows then.
>
> I wonder how C's guaranteed wraparound on unsigned overflow is
> implemented on such machines.

The easiest might be to reduce the size of unsigned values by an
additional bit, then follow each add with a mask?

Terje
--
- <Terje.Mathisen at tmsw.no>
"almost all programming can be viewed as an exercise in caching"

[Kai Harrekilde-Petersen]

Terje Mathisen <"terje.mathisen at tmsw.no"> writes:

> Anton Ertl wrote:
>> If they want to use all the bits for unsigned numbers, then a separate
>> unsigned addition (and subtraction) is needed. However, you can
>> define the positive subset of the signed integers supported by the
>> machine to be the unsigned numbers; then you can use the ordinary
>> (signed) addition for these "unsigned" numbers; but you don't get
>> wrap-around on overflows then.
>>
>> I wonder how C's guaranteed wraparound on unsigned overflow is
>> implemented on such machines.
>
> The easiest might be to reduce the size of unsigned values by an
> additional bit, then follow each add with a mask?

I would be surprised if they do - I guess there must be a simple way of
doing this, since the VHDL standard has been designed so it could be run
on both 1-complement and 2-complement hardware: integer range is limited
to +/-(2**31-1) for this particular reason (at least this is the reason
that is written in textbooks about VHDL).


Kai
--
Kai Harrekilde-Petersen <khp(at)harrekilde(dot)dk>

[Anton Ertl]

nm...@cam.ac.uk writes:
>In article <2011Nov1...@mips.complang.tuwien.ac.at>,
>Anton Ertl <an...@mips.complang.tuwien.ac.at> wrote:
>>>>>
>>>>> >As you probably know, in C unsigned arithmetic is modular. This is
>>>>> >easily implemented in two's complement by ignoring the carry out of
>>>>> >addition.
>>>>>
>>>>> Division and remainder aren't.

...

>Consider 3-bit unsigned integers, for simplicity. 7/5 = 3 in
>true modular arithmetic.

Ok, 3*5=7 (mod 8)

However, with this concept of division, the concept of remainder is
meaningless.

[Michael S]

On Nov 15, 12:12 pm, Luca Forlizzi <luca.forli...@gmail.com> wrote:
> On 15 Nov, 10:29, torb...@diku.dk (Torben Ægidius Mogensen) wrote:
>
> As you probably know, in C unsigned arithmetic is modular. This is
> easily implemented in two's complement by ignoring the carry out of
> addition.

One's complement addition is also modular, with modulo=2**wordsize-1.
Does C standard specify that modulo of unsigned addition/subtraction
has to be power of 2?

[nm...@cam.ac.uk]

In article <fc4566bd-ea00-4112...@g7g2000vbd.googlegroups.com>,

Yes.


Regards,
Nick Maclaren.

[Robert Wessel]

From C99:

"6.2.6.2 Integer types

For unsigned integer types other than unsigned char, the bits of the
object representation shall be divided into two groups: value bits and
padding bits (there need not be any of the latter). If there are N
value bits, each bit shall represent a different power of 2 between 1
and 2N-1, so that objects of that type shall be capable of
representing values from 0 to 2N - 1 using a pure binary
representation; this shall be known as the value representation. The
values of any padding bits are unspecified."

C89 did not specify this quite as explicitly, although it hints at it.