Is there a better way to achieve this ?

[Peter Nilsson]

There's no idiom since people don't do it that often.

But observe the maths...

INT_MIN <= a + b <= INT_MAX
<=> INT_MIN - b <= a <= INT_MAX - b

So, for signed integers...

/* summation overflow */
if (b < 0) { if (a < INT_MIN - b) overflow(); }
else { if (INT_MAX - b < a) overflow(); }

/* subraction overflow */
if (b < 0) { if (INT_MAX + b < a) overflow(); }
else { if (a < INT_MIN + b) overflow(); }

So it is guaranteed by the C standard that in case of
overfllow the result of sum will be less then either
operand?

There is no overflow of unsigned types with a rank of int
or above. [Lower ranks may promote to int in which case
overflow is possible.] But the quoted range check works by
virtue of modulo arithmetic necessary for unsigned int.

It's really quite simple to see. Consider a + b mod 2^n.
Now what non-negative number b would you need to add to a
to make the result larger than a (modulo 2^n)?

 

[James Dow Allen]

Addition of unsigned numbers is well-defined by the C Standard for any
input values; if the mathematical sum of a and b is greater than
UINT_MAX then the result is the mathematical sum (a + b - (UINT_MAX +
1)), which can easily be shown to be less than b in all cases (and
also less than a).

I've not worked on a one's-complement machine since before there
was a C language, but I wonder how they work here. Perhaps
UINT_MAX on such a machine is *two* less than a power-of-two,
rather than *one* less, which would impact the cute number-of-bits
extractor discussed here a year ago. :-(

It isn't called "overflow" because ...

Yes. But it's certainly understandable why *some* might *call*
it overflow. Kudos to Christian who explained this,
rather than just snapping at a "non-compliant usage"
and leaving new c.l.c'ers confused.

<just another useless factoid>
The IBM 370/145 did unsigned arithmetic ("logical arithmetic")
*much* faster than it did signed arithmetic! The data results
are *identical* and both operations set the condition code,
but the condition-code spec for the signed arithmetic
required a microcode detour that took longer than the addition
itself!

Since often one doesn't care about condition code, use of
the logical ops could have sped up some code. No idea if
any programmers were masochisto-perfectionistic enough to
worry about this....
</just another useless factoid>

James Dow Allen

 

[Ben Bacarisse]

I've not worked on a one's-complement machine since before there
was a C language, but I wonder how they work here. Perhaps
UINT_MAX on such a machine is *two* less than a power-of-two,
rather than *one* less, which would impact the cute number-of-bits
extractor discussed here a year ago. :-(

I don't see the issue. All machines that run standard C must use the
same pure binary representation for unsigned ints. The different
signed reps. have no obvious connection to the problem. Is there a
hardware issue you know of to do with implementing full-width pure
binary unsigned ints on a 1's complement system?

Also, unsigned into must be able to hold all the positive values of
signed ints so, if there is an issue, the two-bits shorter solution
is not available.

<snip>

 

[Eric Sosman]

I've not worked on a one's-complement machine since before there
was a C language, but I wonder how they work here. Perhaps
UINT_MAX on such a machine is *two* less than a power-of-two,
rather than *one* less, which would impact the cute number-of-bits
extractor discussed here a year ago. :-(

Yes, I see the smiley, but I'm not sure how much of the
paragraph it applies to. Just in case: *unsigned* integers
do not use two's complement, or ones' complement, or signed
magnitude, all of which are schemes for encoding negative
values. Since unsigned integers cannot have negative values,
the question of how to represent them never arises.

An unsigned integer is represented by some number of value
bits and some number of padding bits (often none at all). The
maximum value is encoded by setting all the value bits to one,
hence that value is necessarily one less than a power of two.
It cannot be two less than a power of two, not never.

We return you now to the usual jesting and hijinks.

 

[James Dow Allen]

No.
(UINT_MAX + 1 == 0) is true
regardless of how negative integers are represented.

I see three responses implying I'm nuts. I wonder if they're
from three people who've never worked with 1's-complement
machines.

Just to be clear, on the one and only one's-complement
machine I've used, there was no special opcode(s) for
*unsigned* integers. And, (pretending for simplicity
that that machine had 16-bit ints) when you added 0xFFFE
to 0x0001 the result was 0x0000. (If you added 0xffff
and 0x0001 the result was 0x0001.) AFAIK there would only
be two conceivable ways to implement a C compiler
on that machine: EITHER make UINT_MAX == 0xfffe OR
every unsigned arithmetic op would require a special
sequence involving tests and multiple machine ops.

I'm guessing the former, but that this got overlooked
in the subthread from a year ago: "Is {U,}{INT,LONG}_MAX
always 1 less than a power-of-two?"

Too bad Dik is no longer with us. Obviously he knew
this stuff like an eagle knows how to fly.

Am I wrong? Is there such a thing as 1's-complement
where 0xffff is *not* "negative zero"?

Note that, if my guess is correct, Pete's response

No.
(UINT_MAX + 1 == 0) is true
regardless of how negative integers are represented.

becomes correct if we simply replace "No." with "Yes."

James Dow Allen

 

[James Dow Allen]

Just to be clear, on the one and only one's-complement
machine I've used, there was no special opcode(s) for
*unsigned* integers.  And, (pretending for simplicity
that that machine had 16-bit ints) when you added 0xFFFE
to 0x0001 the result was 0x0000....

The machine I speak of is the CDC-6{4,5,6}00 with 60-bit
words. Actually, there was another set of opcodes
called "Double Precision Floating Point" opcodes, but which
could also be used for, effectively, unsigned arithmetic.
I *think* only 48-bit results (plus a carry bit) could be
developed. Could C for that machine possibly have had
60-bit signed longs and 48-bit unsigned ints?

Ben and Eric are each correct well over 99% of the time,
so I'm probably going to end up embarrassed by my
outburst. :-(
I'll blame it all on creeping senility: Obviously I wasn't
that stupid 1 year ago, or I would have brought this up
in the "MAX always one less than power-of-two" thread.

James

 

[James Dow Allen]

ISO/IEC 9899:1999 (E)
6.2.5 Types
9
A computation involving unsigned operands can never overflow,
because a result that cannot be represented by the resulting
unsigned integer type is reduced modulo the number that is
one greater than the largest value
that can be represented by the resulting type.

Yes. Everything you've written is compatible with BOTH
possibilities I've raised except for the single word "No"
in your first response which becomes "Yes" in the peculiar
variation I've outlined. (Note that the "modulo"
you mention would then be *1 less than a power-of-two*!)

If my perspective is still unclear, know this: I'm far
more interested in the behaviour of the C compiler on a
Real Machine with 1's-complement arithmetic than
I am in the specific diction of an ISO document.

As I imply in my recent post, I'm starting to guess the
CDC 6{4,5,6}00 used 48-bit unsigned ints that behaved
as normal 2's-complement integers behave, and special
coding for unsigned longs, if any, of some larger size.

James

 

[Tim Rentsch]

I see three responses implying I'm nuts. I wonder if they're
from three people who've never worked with 1's-complement
machines.

Just to be clear, on the one and only one's-complement
machine I've used, there was no special opcode(s) for
*unsigned* integers. And, (pretending for simplicity
that that machine had 16-bit ints) when you added 0xFFFE
to 0x0001 the result was 0x0000. (If you added 0xffff
and 0x0001 the result was 0x0001.) AFAIK there would only
be two conceivable ways to implement a C compiler
on that machine: EITHER make UINT_MAX == 0xfffe OR
every unsigned arithmetic op would require a special
sequence involving tests and multiple machine ops.

That doesn't matter, because the Standard requires
unsigned types with N value bits to represent all
values between 0 and 2**N - 1.

I'm guessing the former, but that this got overlooked
in the subthread from a year ago: "Is {U,}{INT,LONG}_MAX
always 1 less than a power-of-two?"

Yes.

(Honesty in advertsing: some people have argued that
the signed maximums INT_MAX or LONG_MAX don't have to
be one less than a power of two. I disagree. However,
about the unsigned types the Standard is quite clear,
and as far as I know there is no disagreement there.)

 

[Eric Sosman]

I see three responses implying I'm nuts. I wonder if they're
from three people who've never worked with 1's-complement
machines.

(1) Not "nuts," just "mistaken." (2) I've worked with a
ones' complement machine, although only briefly and not in C.

Just to be clear, on the one and only one's-complement
machine I've used, there was no special opcode(s) for
*unsigned* integers. And, (pretending for simplicity
that that machine had 16-bit ints) when you added 0xFFFE
to 0x0001 the result was 0x0000. (If you added 0xffff
and 0x0001 the result was 0x0001.) AFAIK there would only
be two conceivable ways to implement a C compiler
on that machine: EITHER make UINT_MAX == 0xfffe OR
every unsigned arithmetic op would require a special
sequence involving tests and multiple machine ops.

6.2.6.2p1: "For unsigned integer types [...] objects of
that type shall be capable of representing values from 0 to
2^N - 1 using a pure binary representation [...]"

An implementation might need to jump through hoops to
make this happen on unfriendly hardware, just as implementations
on word-addressed machines must jump through hoops to use
pointers to smaller-than-word types. That's the implementation's
problem, and the implementation's duty.

I'm guessing the former, but that this got overlooked
in the subthread from a year ago: "Is {U,}{INT,LONG}_MAX
always 1 less than a power-of-two?"

Too bad Dik is no longer with us. Obviously he knew
this stuff like an eagle knows how to fly.

Am I wrong? Is there such a thing as 1's-complement
where 0xffff is *not* "negative zero"?

There could be a machine for which that bit pattern would
be a trap representation (for a signed integer), with no value
at all. If it's not a trap, though, it's negative zero on a
ones' complement machine.

... which makes no nevermind for *unsigned* types, which
do not encode a sign at all, not with any of the schemes that
are used for signed integers, nor with any other scheme.

 

[Ben Bacarisse]

These machines had very limited integer arithmetic on 60-bit fixed
point numbers. There was (if I am not mistaken) no multiply or divide
for example.

C on a CDC would have other problems. All the ones I know of have 6
bit characters and at least 8 are required for C. There is no byte
addressing so the compiler would have to emulate (a) wider characters,
(b) unsigned arithmetic, (c) integer multiply, divide and remainder
(if it opted to use the 60-bit number format) as well as (d) void *
and char *.

(a) and (d) can be solved by the very clumsy expedient of having
60-bit characters but, given the storage limits these machines had, no
one would do that.

The machine I speak of is the CDC-6{4,5,6}00 with 60-bit
words. Actually, there was another set of opcodes
called "Double Precision Floating Point" opcodes, but which
could also be used for, effectively, unsigned arithmetic.
I *think* only 48-bit results (plus a carry bit) could be
developed. Could C for that machine possibly have had
60-bit signed longs and 48-bit unsigned ints?

You'd still have a problem with unsigned long. For every signed type
there must be an unsigned type with at least as many value bits.

<snip>

 

[Mark]

But observe the maths...

INT_MIN <= a + b <= INT_MAX
<=> INT_MIN - b <= a <= INT_MAX - b

So, for signed integers...

[snip]

Thanks, Peter and Christian. Indeed it's simple. Sometimes the most obvious
solution is on a surface, but one would look it up beneath the surface