Asp Forum - Subtracting two big unsigned numbers

pozz

6/9/2011 8:11:00 PM

What happens when I sum or subtract two unsigned integers? I think the
operands are considered unsigned, because they are of the same type.

When I sum two unsigned integers the only problem could be an overflow.
When I subtract a lower from a bigger number, I won't have any problem.

The problem is when I subtract a bigger from a lower number. If they are
"small" numbers (lower or equal than INT_MAX), I can cast to (signed
int). What happens when I subtract INT_MAX+1 from INT_MAX+2?

unsigned int x = INT_MAX + 2U;
unsigned int y = INT_MAX + 1U;
int diff = y - x;
printf("diff=%d\n", diff);

I tried with one compiler and I obtain the correct result: diff=-1.
Is this a standard behaviour or is it implementation defined/undefined
behaviour?

(y - x) is a binary expression between two unsigned variables, so they
shouldn't be changed into signed variables. So the result should be
always unsigned... so what happens to -1?

11 Answers

Thomas Richter

6/9/2011 8:32:00 PM

On 09.06.2011 22:10, pozz wrote:
> What happens when I sum or subtract two unsigned integers?

The result is computed modulo 2^N.

> I think the
> operands are considered unsigned, because they are of the same type.

Yes.

> When I sum two unsigned integers the only problem could be an overflow.

Not in the sense that the result is undefined. The result will
wrap-around in a well-defined way. unsigned integers implement modulo
arithmetic. Overflows happen with signed arithmetic, and what happens
there is up to the implementation (including possibly a trap).

> When I subtract a lower from a bigger number, I won't have any problem.
>
> The problem is when I subtract a bigger from a lower number. If they are
> "small" numbers (lower or equal than INT_MAX), I can cast to (signed
> int). What happens when I subtract INT_MAX+1 from INT_MAX+2?

INT_MAX is not an unsigned number. You can first convert it to an
unsigned number, and then subtract. In that case, the result is +1,
always, and defined to be +1 for any conforming compiler. Note that this
is not guaranteed for signed integers.

> unsigned int x = INT_MAX + 2U;
> unsigned int y = INT_MAX + 1U;
> int diff = y - x;

This is not what you're writing above. Here you subtract INT_MAX
converted to unsigned, plus 2, from a INT_MAX+1. The result is the
largest possible unsigned number. You then convert it to a signed type
that cannot represent this value. What happens then is not defined by
the ANSI standard, but rather implementation defined. In your specific
case, with your specific compiler, complement arithmetic is used and the
result is interpreted as negative number modulo a power of two. But this
is, as said, not guaranteed by ANSI C, but (should be) by your compiler.

> printf("diff=%d\n", diff);
>
> I tried with one compiler and I obtain the correct result: diff=-1.
> Is this a standard behaviour or is it implementation defined/undefined
> behaviour?

It is implementation defined. x-y = 1U and y-x=MAX_UINT is standard defined.

> (y - x) is a binary expression between two unsigned variables, so they
> shouldn't be changed into signed variables.

So why do you convert it to a signed variable in first place? (-; You
are quite correct, the difference is indeed an unsigned int.

> So the result should be
> always unsigned... so what happens to -1?

A conversion of a valid value of an unsigned int which is not
representable by signed int. Up to the implementation to define what
then happens. For a machine using sign-magnitude representations for
ints, the result might possibly be the smallest (largest in absolute
value) negative number reprsentable by int, not -1.

unsigned int diff = y - x;

gives the right result, namely -1 + 2^N, for a suitable value of N.
Where N is, of course, defined by the implementation. However, *that*
you have modulo arithmetic here is, indeed, ensured by ANSI-C.

HTHH,
Thomas

pozz

6/9/2011 9:07:00 PM

Il 09/06/2011 22:32, Thomas Richter ha scritto:
>> unsigned int x = INT_MAX + 2U;
>> unsigned int y = INT_MAX + 1U;
>> int diff = y - x;
>
> This is not what you're writing above. Here you subtract INT_MAX
> converted to unsigned, plus 2, from a INT_MAX+1. The result is the
> largest possible unsigned number. You then convert it to a signed type
> that cannot represent this value. What happens then is not defined by
> the ANSI standard, but rather implementation defined. In your specific
> case, with your specific compiler, complement arithmetic is used and the
> result is interpreted as negative number modulo a power of two. But this
> is, as said, not guaranteed by ANSI C, but (should be) by your compiler.

Ok, so how should I code a difference between two unsigned int values in
order to avoid implementation defined behaviour?

This problem happened when I tried to write a simple timer driver for an
embedded platform. I have a volatile unsigned int variable that
increments every clock tick (inside an interrupt):

volatile unsigned int ticks;

ticks is a global variable that goes from 0x0000 to 0xFFFF and
wrap-around again to 0x0000 (on 16 bit platforms).
If I want to wait for 1000 clock ticks, starting from now, I can do this:

extern volatile unsigned int ticks;
unsigned int timer = ticks + 1000;
while (ticks < timer) {
/* wait... */
}

Apparently this work, but it doesn't. Suppose ticks is 65000, so timer
is 66000 - 65536 = 464. Even immediately, ticks is greater than timer
and the wait isn't performed as desired.

The solution could be:

while ((int)(ticks - timer) < 0) {
/* wait... */
}

Considering the example above, 65000(ticks) - 464(timer) = 64536. This
value is converted in an implementation defined way to a signed int, but
usually it will be 64536 - 65536 = -1000. This value is negative and the
wait is performed as desired.
As soon as ticks will be 464, the result of the difference will be 0 and
the while test condition will be false (the waiting period will be expired).

So this approach solves my initial problem, but it is implementation
defined (even if I think it'll work on several machines).
Do you suggest a better approach without implementation defined code?

Of course, the maximum allowable waiting period will be 32767.

I'm thinking about this:

while (ticks - timer > (unsigned)INT_MAX) {
/* wait... */
}

What do you think?

Keith Thompson

6/9/2011 9:23:00 PM

pozz <pozzugno@gmail.com> writes:
> What happens when I sum or subtract two unsigned integers? I think the
> operands are considered unsigned, because they are of the same type.
>
> When I sum two unsigned integers the only problem could be an overflow.

Strictly speaking, "overflow" isn't an issue for unsigned integers. If
the mathematical result is outside the representable range, it's reduced
modulo MAX+1. (It's reasonable to call this "overflow", but the
standard doesn't.)

C99 6.2.5p9:

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.

> When I subtract a lower from a bigger number, I won't have any problem.
>
> The problem is when I subtract a bigger from a lower number. If they are
> "small" numbers (lower or equal than INT_MAX), I can cast to (signed
> int). What happens when I subtract INT_MAX+1 from INT_MAX+2?
>
> unsigned int x = INT_MAX + 2U;

INT_MAX is converted from int to unsigned int and added to 2U.
(Note that without the "U" suffix, this would be an int addition,
with undefined behavior due to overflow.) In short, yes, this does
what you want.

> unsigned int y = INT_MAX + 1U;
> int diff = y - x;

This is easier to understand if you split it into two parts:

int udiff = y - x; /* unsigned subtraction */
int diff = udiff; /* implicit conversion from unsigned int to int */

The mathematical result of y - x would be -1. Since -1 is outside the
range of values it's "reduced" as described above, resulting in
UINT_MAX.

UINT_MAX is then converted from unsigned int to int. The rules
for conversion to a signed type are different from the rules
for an unsigned type; if the value doesn't fit, the result is
implementation-defined (or an implementation-defined signal is
raised). The behavior you're seeing, converting UINT_MAX to -1,
is very common, but it's not required.

> printf("diff=%d\n", diff);
>
> I tried with one compiler and I obtain the correct result: diff=-1.
> Is this a standard behaviour or is it implementation defined/undefined
> behaviour?

It's implementation-defined.

> (y - x) is a binary expression between two unsigned variables, so they
> shouldn't be changed into signed variables. So the result should be
> always unsigned... so what happens to -1?

Yes, the result of (y - x) is unsigned, but you converted that unsigned
result to a signed type.

--
Keith Thompson (The_Other_Keith) kst-u@mib.org <http://www.ghoti.ne...
Nokia
"We must do something. This is something. Therefore, we must do this."
-- Antony Jay and Jonathan Lynn, "Yes Minister"

pozz

6/9/2011 9:31:00 PM

Il 09/06/2011 23:23, Keith Thompson ha scritto:
>> unsigned int y = INT_MAX + 1U;
>> int diff = y - x;
>
> This is easier to understand if you split it into two parts:
>
> int udiff = y - x; /* unsigned subtraction */
> int diff = udiff; /* implicit conversion from unsigned int to int */
>
> The mathematical result of y - x would be -1. Since -1 is outside the
> range of values it's "reduced" as described above, resulting in
> UINT_MAX.
>
> UINT_MAX is then converted from unsigned int to int. The rules
> for conversion to a signed type are different from the rules
> for an unsigned type; if the value doesn't fit, the result is
> implementation-defined (or an implementation-defined signal is
> raised). The behavior you're seeing, converting UINT_MAX to -1,
> is very common, but it's not required.

Ok, thank you for your explanation. Could you suggest a solution for my
problem descripted in the second post of mine in the same thread?

Peter Nilsson

6/10/2011

pozz <pozzu...@gmail.com> wrote:
> Keith Thompson ha scritto:
> > [snip good answer to wrong question that excluded the problem]
>
> Ok, thank you for your explanation. Could you suggest a solution
> for my problem descripted in the second post of mine in the same
> thread?

Usenet doesn't guarantee that every server receives every post.
So you should not assume Keith (or clc readers in general) have
received your other post.

Citing your other post:

> ...I have a volatile unsigned int variable that
> increments every clock tick (inside an interrupt):
>
> volatile unsigned int ticks;
>
> ticks is a global variable that goes from 0x0000 to 0xFFFF
> and wrap-around again to 0x0000 (on 16 bit platforms).
> If I want to wait for 1000 clock ticks, starting from now,
> I [tried] this:
>
> extern volatile unsigned int ticks;
> unsigned int timer = ticks + 1000;
> while (ticks < timer) {
> /* wait... */
> }

Consider the cases...

Normal:
From: ---start->>tick>>-end----------
Exit: ---start----------end->>tick>>-

Wrap:
From: ----------end----------start->>tick>>-
Wrap: ->>tick>>-end----------start----------
Exit: ----------end->>tick>>-start----------

unsigned int start = ticks;
unsigned int end = start + end;
while (tick < end || (end < start && start <= tick))
...wait...

--
Peter

pozz

6/10/2011 6:50:00 AM

On 10 Giu, 02:00, Peter Nilsson <ai...@acay.com.au> wrote:
> > ...I have a volatile unsigned int variable that
> > increments every clock tick (inside an interrupt):
> >
> > volatile unsigned int ticks;
> >
> > ticks is a global variable that goes from 0x0000 to 0xFFFF
> > and wrap-around again to 0x0000 (on 16 bit platforms).
> > If I want to wait for 1000 clock ticks, starting from now,
> > I [tried] this:
> >
> > extern volatile unsigned int ticks;
> > unsigned int timer = ticks + 1000;
> > while (ticks < timer) {
> > /* wait... */
> > }
>
> Consider the cases...
>
> Normal:
> From: ---start->>tick>>-end----------
> Exit: ---start----------end->>tick>>-
>
> Wrap:
> From: ----------end----------start->>tick>>-
> Wrap: ->>tick>>-end----------start----------
> Exit: ----------end->>tick>>-start----------
>
> unsigned int start = ticks;
> unsigned int end = start + end;
> while (tick < end || (end < start && start <= tick))
> ...wait...

With your solution, I would have to use an additional variable, start.

What about my last option?

while (ticks - timer > (unsigned)INT_MAX) {
/* wait... */
}

It seems it always works well without implementation defined or
undefined behaviour.

James Kuyper

6/10/2011 11:04:00 AM

On 06/09/2011 05:07 PM, pozz wrote:
....
> This problem happened when I tried to write a simple timer driver for an
> embedded platform. I have a volatile unsigned int variable that
> increments every clock tick (inside an interrupt):
>
> volatile unsigned int ticks;
>
> ticks is a global variable that goes from 0x0000 to 0xFFFF and
> wrap-around again to 0x0000 (on 16 bit platforms).
> If I want to wait for 1000 clock ticks, starting from now, I can do this:
>
> extern volatile unsigned int ticks;
> unsigned int timer = ticks + 1000;
> while (ticks < timer) {
> /* wait... */
> }
>
> Apparently this work, but it doesn't. Suppose ticks is 65000, so timer
> is 66000 - 65536 = 464. Even immediately, ticks is greater than timer
> and the wait isn't performed as desired.
>
> The solution could be:
>
> while ((int)(ticks - timer) < 0) {
> /* wait... */
> }
>
> Considering the example above, 65000(ticks) - 464(timer) = 64536. This
> value is converted in an implementation defined way to a signed int, but
> usually it will be 64536 - 65536 = -1000. This value is negative and the
> wait is performed as desired.
> As soon as ticks will be 464, the result of the difference will be 0 and
> the while test condition will be false (the waiting period will be expired).
>
> So this approach solves my initial problem, but it is implementation
> defined (even if I think it'll work on several machines).
> Do you suggest a better approach without implementation defined code?
>
> Of course, the maximum allowable waiting period will be 32767.
>
> I'm thinking about this:
>
> while (ticks - timer > (unsigned)INT_MAX) {
> /* wait... */
> }
>
> What do you think?

This is an improvement, in that (unsigned)INT_MAX always has a
well-defined value for any given implementation; but that value could,
in principle, differ from one implementation to another. In practice, of
course, if UINT_MAX is 0xFFFF, then INT_MAX is almost certainly going to
be 0x7FFF. [1] However, what you want to do has nothing to do with the
properties of signed int, so you shouldn't be expressing it in terms of
INT_MAX, even if that connection were perfectly guaranteed.

The key point to consider is why the timer wraps around at 0xFFFF. That
happens to be UINT_MAX on the 16-bit implementation you're describing.
Would it be inappropriate to port this code to a implementation where
UINT_MAX was larger than that? Then I'd recommend adding the following:

#if UINT_MAX > 0xFFFF
#error Your explanation of why this code should not be ported.
#endif

If it would be appropriate to port this code to an implementation where
UINT_MAX > 0xFFFF, do you still want the time to wrap around at 0xFFFF?
In that case, you should use

while((ticks - timer) & 0xFFFF > 0x7FFF)

That may look wasteful, but any decent compiler will optimize the mask
operation away, on platforms where UINT_MAX == 0xFFFF.

Alternatively, would you want the calculation to wrap around at
UINT_MAX, even if UINT_MAX > 0xFFFF? then you should use

while((ticks - timer) > UINT_MAX/2)

[1] In principle, 'int' could be a 17-bit type, and the sign bit of
'int' could be a padding bit for unsigned int, but it's exceedingly
unlikely that such an implementation would ever be created for any
reason other than to prove that principle.
--
James Kuyper

pozz

6/10/2011 8:02:00 PM

Il 10/06/2011 13:04, James Kuyper ha scritto:
> Alternatively, would you want the calculation to wrap around at
> UINT_MAX, even if UINT_MAX> 0xFFFF?

You got it... I'm not interested when the counter wrap around. It could
be at 0xFFFF (my actual platform), but it could be at 0xFFFFFFFF (the
next platforum).

> then you should use
>
> while((ticks - timer)> UINT_MAX/2)

This is somewhat similar to my solution, except you use UINT_MAX/2 while
I have used INT_MAX. I thought they were the same value.

James Kuyper

6/11/2011 3:02:00 AM

On 06/10/2011 04:01 PM, pozz wrote:
> Il 10/06/2011 13:04, James Kuyper ha scritto:
....
>> then you should use
>>
>> while((ticks - timer)> UINT_MAX/2)
>
> This is somewhat similar to my solution, except you use UINT_MAX/2 while
> I have used INT_MAX. I thought they were the same value.

They usually are, but they're not required to be. The only relevant
connection between those two values that is imposed by the C standard is
that UINT_MAX >= INT_MAX.

How would you want your code to behave, if compiled by an implementation
where UINT_MAX/2 and INT_MAX are not the same? You don't have to worry
about that question if you don't want to; it an extremely implausible
possibility. But if that possibility were to come up, I think that
UINT_MAX/2 would be more appropriate than INT_MAX.
--
James Kuyper

Tim Rentsch

6/14/2011 10:21:00 PM

Keith Thompson <kst-u@mib.org> writes:

[snip]
> This is easier to understand if you split it into two parts:
>
> int udiff = y - x; /* unsigned subtraction */
> int diff = udiff; /* implicit conversion from unsigned int to int */
>
> [snip]

Of course you meant 'unsigned int udiff = y - x;'.

(I know you put these in just to see if people are
paying attention. :)

comp.lang.c

Subtracting two big unsigned numbers

pozz

Thomas Richter

pozz

Keith Thompson

pozz

Peter Nilsson

pozz

James Kuyper

pozz

James Kuyper

Tim Rentsch

x Login to ForumsZone