Subtracting unsigned entities

[fred.l.kleinschmidt@boeing.com]

If one knows that x and y are unsigned integers (of unknown size -
they may be short, int, long, long long), what is the most portable
way to determine their difference?

If x is smaller than y, then x-y is negative.

A naive approach is
if ( x y ) {
...
}

but a compiler may code (x>y) as (x-y 0).

--
Fred Kleinschmidt
Boeing Aero C&S

[Richard Heathfield]

Re: Subtracting unsigned entities

fred.l.kleinsch midt@boeing.com said:

If one knows that x and y are unsigned integers (of unknown size -
they may be short, int, long, long long), what is the most portable
way to determine their difference?
>
If x is smaller than y, then x-y is negative.
>
A naive approach is
if ( x y ) {
...
}

Why is that naive?

>
but a compiler may code (x>y) as (x-y 0).

No, it can't do that if it won't produce the correct result.

--
Richard Heathfield <http://www.cpax.org.uk >
Email: -http://www. +rjh@
Google users: <http://www.cpax.org.uk/prg/writings/googly.php>
"Usenet is a strange place" - dmr 29 July 1999

[Ben Pfaff]

Re: Subtracting unsigned entities

fred.l.kleinsch midt@boeing.com writes:

If one knows that x and y are unsigned integers (of unknown size -
they may be short, int, long, long long), what is the most portable
way to determine their difference?
>
If x is smaller than y, then x-y is negative.

Mathematically, yes. But in C, the difference of two values of
type unsigned int is always nonnegative.

A naive approach is
if ( x y ) {
...
}
>
but a compiler may code (x>y) as (x-y 0).

No, the compiler is obliged to produce the correct result.
--
"The way I see it, an intelligent person who disagrees with me is
probably the most important person I'll interact with on any given
day."
--Billy Chambless

[=?ISO-8859-1?Q?Tom=E1s_=D3_h=C9ilidhe?=]

Re: Subtracting unsigned entities

On May 12, 11:18 pm, fred.l.kleinsch m...@boeing.com wrote:

If one knows that x and y are unsigned integers (of unknown size -
they may be short, int, long, long long), what is the most portable
way to determine their difference?

Let's take an example:

unsigned x, y;

x = 65530u;
y = 655u;

The difference between these two is 64875.

If you do (x-y), you'll get 64875u. However if you do (y-x), you'll
get an implementation-defined value which depends on the value of
UINT_MAX (because when you go past zero you'll start counting backward
from UINT_MAX).

If x is smaller than y, then x-y is negative.
>
A naive approach is
   if ( x y ) {
      ...
   }
>
but a compiler may code (x>y) as  (x-y 0)

The if method is the only one that comes to mind.

[Bart]

Re: Subtracting unsigned entities

On May 12, 11:18 pm, fred.l.kleinsch m...@boeing.com wrote:

If one knows that x and y are unsigned integers (of unknown size -
they may be short, int, long, long long), what is the most portable
way to determine their difference?
>
If x is smaller than y, then x-y is negative.
>
A naive approach is
   if ( x y ) {
      ...
   }
>
but a compiler may code (x>y) as  (x-y 0).

What do you mean by difference?

If you mean x-y, then this will give strange results when x<y (it
can't be negative).

If you mean max(x,y)-min(x,y) then your 'naive' approach will likely
work well.

--
Bartc

[Peter Nilsson]

Re: Subtracting unsigned entities

Bart wrote:

fred.l.kleinsch m...@boeing.com wrote:

If one knows that x and y are unsigned integers (of unknown
size - they may be short, int, long, long long), what is the
most portable way to determine their difference?

Subtraction. Though that need not be the minimum 'distance'
metric.

If x is smaller than y, then x-y is negative.

A naive approach is
if ( x y ) {
...
}

but a compiler may code (x>y) as (x-y 0).

>
What do you mean by difference?
>
If you mean x-y, then this will give strange results when x<y (it
can't be negative).

It can in some circumstances, e.g. USHRT_MAX < INT_MAX.

--
Peter

[Chris Dollin]

Re: Subtracting unsigned entities

fred.l.kleinsch midt@boeing.com wrote:

If one knows that x and y are unsigned integers (of unknown size -
they may be short, int, long, long long), what is the most portable
way to determine their difference?
>
If x is smaller than y, then x-y is negative.
>
A naive approach is
if ( x y ) {
...
}
>
but a compiler may code (x>y) as (x-y 0).

It might code it as `x + 17`, too, but if it wants to be correct
both decisions would be suspect.

--
"Why, /yes/, madame. Certainly. Now?" - Lois McMaster Bujold /A Civil Campaign/

Hewlett-Packard Limited Cain Road, Bracknell, registered no:
registered office: Berks RG12 1HN 690597 England

[fred.l.kleinschmidt@boeing.com]

Re: Subtracting unsigned entities

On May 12, 3:58 pm, Bart <b...@freeuk.co mwrote:

On May 12, 11:18 pm, fred.l.kleinsch m...@boeing.com wrote:
>

If one knows that x and y are unsigned integers (of unknown size -
they may be short, int, long, long long), what is the most portable
way to determine their difference?

>

If x is smaller than y, then x-y is negative.

>

A naive approach is
   if ( x y ) {
      ...
   }

>

but a compiler may code (x>y) as  (x-y 0).

>
What do you mean by difference?
>
If you mean x-y, then this will give strange results when x<y (it
can't be negative).
>
If you mean max(x,y)-min(x,y) then your 'naive' approach will likely
work well.
>

The problem came up on a Unix platform, where some code was trying
to check for a double-click. Each time button1 is clicked, it checks
the time with the previous time it was clicked; if the difference is
small enough, a double-click is assumed.

The times are stored in a variable of type Time, defined as
an unsigned int on some platforms, unsigned long on others, storing
clock time in milliseconds.

For an unsigned int, the value will wrap every 47 days. The original
code was

if ( (newtime - oldtime) < doubleclicktime ) {
/* perform double-click action */
}

That code is unsafe: as oldtime approaches UINT_MAX, the risk
is that newtime might occur after time wraps, thus might be
a small integer, and (newtime - oldtime) is mathematically
negative.

Since others have said that the compiler is obliged to
perform the if-test properly, my solution is

if ( t2 t1 ) {
delta = t2 - t1;
}
else {
delta = (UINT_MAX - t1) + t2 + 1;
}

--
Fred Kleinschmidt

[Eric Sosman]

Re: Subtracting unsigned entities

fred.l.kleinsch midt@boeing.com wrote:

On May 12, 3:58 pm, Bart <b...@freeuk.co mwrote:

>On May 12, 11:18 pm, fred.l.kleinsch m...@boeing.com wrote:
>>

>>If one knows that x and y are unsigned integers (of unknown size -
>>they may be short, int, long, long long), what is the most portable
>>way to determine their difference?
>>If x is smaller than y, then x-y is negative.
>>A naive approach is
>> if ( x y ) {
>> ...
>> }
>>but a compiler may code (x>y) as (x-y 0).

>What do you mean by difference?
>>
>If you mean x-y, then this will give strange results when x<y (it
>can't be negative).
>>
>If you mean max(x,y)-min(x,y) then your 'naive' approach will likely
>work well.
>>

>
The problem came up on a Unix platform, where some code was trying
to check for a double-click. Each time button1 is clicked, it checks
the time with the previous time it was clicked; if the difference is
small enough, a double-click is assumed.
>
The times are stored in a variable of type Time, defined as
an unsigned int on some platforms, unsigned long on others, storing
clock time in milliseconds.
>
For an unsigned int, the value will wrap every 47 days. The original
code was
>
if ( (newtime - oldtime) < doubleclicktime ) {
/* perform double-click action */
}
>
That code is unsafe: as oldtime approaches UINT_MAX, the risk
is that newtime might occur after time wraps, thus might be
a small integer, and (newtime - oldtime) is mathematically
negative.

Doesn't matter. You've said the times are either
`unsigned int' or `unsigned long' depending on the platform,
and neither of these is subject to promotion. Hence, the
arithmetic will be carried out according to the unsigned
rules, and `tiny - huge' will yield `moderate', as desired.

Since others have said that the compiler is obliged to
perform the if-test properly, my solution is
>
if ( t2 t1 ) {
delta = t2 - t1;
}
else {
delta = (UINT_MAX - t1) + t2 + 1;
}

The `else' clause is just an obfuscated version of
the `then' clause, producing the same result.

--
Eric.Sosman@sun .com

[Chris Dollin]

Re: Subtracting unsigned entities

fred.l.kleinsch midt@boeing.com wrote:

Since others have said that the compiler is obliged to
perform the if-test properly, my solution is
>
if ( t2 t1 ) {
delta = t2 - t1;
}
else {
delta = (UINT_MAX - t1) + t2 + 1;
}

Not
if (t2 t1) delta = t2 - t1;
else delta = t1 - t2;

? Because that seems simpler and at least as correct.

(Of course I'd write it as

delta = t2 t1 ? t2 - t1 : t1 - t2;

)

--
/Questions? Answers! Answers? Questions!/ - Focus

Hewlett-Packard Limited registered office: Cain Road, Bracknell,
registered no: 690597 England Berks RG12 1HN

[=?iso-8859-1?Q?=D8yvind_R=F8tvold?=]

Re: Subtracting unsigned entities

fred.l.kleinsch midt@boeing.com writes:

On May 12, 3:58 pm, Bart <b...@freeuk.co mwrote:

[ snip ]

For an unsigned int, the value will wrap every 47 days. The original
code was
>
if ( (newtime - oldtime) < doubleclicktime ) {
/* perform double-click action */
}
>
That code is unsafe:

No.

as oldtime approaches UINT_MAX, the risk
is that newtime might occur after time wraps, thus might be
a small integer,

Yes.

and (newtime - oldtime) is mathematically negative.

If newtime and oldtime are of the same unsigned type, the result will
never be negative, and (newtime - oldtime) will be the correct time
difference even when there's a wrap. Assuming ofcourse that the timer
wraps correctly, this will work in any kind of modulo arithmetic.
Whoever made this code originally probably knew what he was doing.

[ snip ]

--
... __o Øyvind
... _`\(, http://www.darkside.no/olr/
... (_)/(_) ... biciclare necesse est ...

[Harald van =?UTF-8?b?RMSzaw==?=]

Re: Subtracting unsigned entities

On Tue, 13 May 2008 22:55:41 +0200, Øyvind Røtvold wrote:

fred.l.kleinsch midt@boeing.com writes:

>On May 12, 3:58 pm, Bart <b...@freeuk.co mwrote:

[ snip ]

>For an unsigned int, the value will wrap every 47 days. The original
>code was
>>
> if ( (newtime - oldtime) < doubleclicktime ) {
> /* perform double-click action */
> }
>>
>That code is unsafe:

>
No.
>

>as oldtime approaches UINT_MAX, the risk is that newtime might occur
>after time wraps, thus might be a small integer,

>
Yes.
>

>and (newtime - oldtime) is mathematically negative.

>
If newtime and oldtime are of the same unsigned type, the result will
never be negative, and (newtime - oldtime) will be the correct time
difference even when there's a wrap.

If newtime and oldtime are of the same unsigned type, *and that unsigned
type is unsigned int or wider*, then yes. It is unsigned int here,
apparently, so then it is safe, but it's not safe with smaller unsigned
types. If they were of type unsigned short, for example, it's very well
possible for newtime - oldtime to produce a negative result, because
newtime and oldtime will be promoted, typically to signed int, before any
subtraction takes place.