unsigned abs(int)?

(This might be an FAQ.) What is the portable way, if any, to
define a function

unsigned abs( int )

that returns the correct value especially also for INT_MIN?
»Portable« includes that it works both with two's-complement
and with one's-complement representation and with any ranges
of int and unsigned permitted by C.

ram@zedat.fu-berlin.de (Stefan Ram) writes:

> (This might be an FAQ.) What is the portable way, if any, to
> define a function
>
> unsigned abs( int )
>
> that returns the correct value especially also for INT_MIN?
> »Portable« includes that it works both with two's-complement
> and with one's-complement representation and with any ranges
> of int and unsigned permitted by C.

C allows and implementation in which UINT_MAX == INT_MAX and where,
simultaneously, -INT_MAX > INT_MIN (indeed such implementations exist).
As a result, the mathematical value of abs(INT_MIN) need not be
representable as an unsigned int. I don't think an entirely portable,
correct function exists with the given prototype.

--
Ben.

ram@zedat.fu-berlin.de (Stefan Ram) writes:

> (This might be an FAQ.) What is the portable way, if any, to
> define a function
>
> unsigned abs( int )
>
> that returns the correct value especially also for INT_MIN?
> >>Portable<< includes that it works both with two's-complement
> and with one's-complement representation and with any ranges
> of int and unsigned permitted by C.

unsigned
unsigned_abs( int n ){
return n >= 0 ? n : -(n+1) + 1UL;
}

Note that for implementations where UINT_MAX == INT_MAX,
and where INT_MIN == -INT_MAX - 1 (which must be two's
complement), there is no unsigned int value that's right.
Under these conditions, unsigned_abs( INT_MIN ) gives zero.
In all other cases it gives the right value.

(Am I confused or is abs() the name of a standard library
function?)

Tim Rentsch <txr@alumni.caltech.edu> writes:
>unsigned
>unsigned_abs( int n ){
> return n >= 0 ? n : -(n+1) + 1UL;
>}
>Note that for implementations where UINT_MAX == INT_MAX,
>and where INT_MIN == -INT_MAX - 1 (which must be two's
>complement), there is no unsigned int value that's right.
>Under these conditions, unsigned_abs( INT_MIN ) gives zero.
>In all other cases it gives the right value.

I was asking because some implementations of »itoa« start
with something like:

if( n < 0 ){ n = -n; *p++ = '-'; }

, but then seem to fail sometimes for INT_MIN.

I was wondering whether there is a portable implementation
that will be correct for all int values.

One could set a flag when n == INT_MIN and then
convert (n+1). Eventually one would do the »+1«
on the string buffer, possibly with a carry value.

>(Am I confused or is abs() the name of a standard library
>function?)

Well, let's say that, er, I was thinking of a freestanding
implementation.

On 7/1/2012 2:27 PM, Stefan Ram wrote:
> Tim Rentsch <txr@alumni.caltech.edu> writes:
>> unsigned
>> unsigned_abs( int n ){
>> return n >= 0 ? n : -(n+1) + 1UL;
>> }
>> Note that for implementations where UINT_MAX == INT_MAX,
>> and where INT_MIN == -INT_MAX - 1 (which must be two's
>> complement), there is no unsigned int value that's right.
>> Under these conditions, unsigned_abs( INT_MIN ) gives zero.
>> In all other cases it gives the right value.
>
> I was asking because some implementations of »itoa« start
> with something like:
>
> if( n < 0 ){ n = -n; *p++ = '-'; }
>
> , but then seem to fail sometimes for INT_MIN.
>
> I was wondering whether there is a portable implementation
> that will be correct for all int values.

PJ Plauger's "The Standard C Library" shows one way to handle
the task, in the underpinnings of printf() et al. Basically, he
converts a negative value to `unsigned long', negates that value
in `unsigned long' arithmetic, and uses the result to produce the
leading digit. Then he strips the leading digit from the value
being converted (without the leading digit it must be >LONG_MIN)
and proceeds straightforwardly through any remaining digits.

Another way would be to start with something like

if (n > 0) n = -n; else *p++ = '-';

.... and work in negative numbers all the way. This is a little
trickier in C90 than in C99/C11, because in the former `-13 % 10'
could be -3 or +7, while in the later Standards it is always -3.

--
Eric Sosman
esosman@ieee-dot-org.invalid

Stefan Ram wrote:
> I was asking because some implementations of »itoa« start
> with something like:
>
> if( n < 0 ){ n = -n; *p++ = '-'; }
>
> , but then seem to fail sometimes for INT_MIN.
>
> I was wondering whether there is a portable implementation
> that will be correct for all int values.
>
> One could set a flag when n == INT_MIN and then
> convert (n+1). Eventually one would do the »+1«
> on the string buffer, possibly with a carry value.


#include <limits.h>

void
itoa(int n, char *s)
{
int tenth, min_offset;
char *p, swap;

min_offset = 0;
if (0 > n) {
if (-INT_MAX > n) {
++n;
++min_offset;
}
n = -n;
*s++ = '-';
}
p = s;
tenth = n;
do {
tenth /= 10;
*p++ = (char)(n - 10 * tenth + '0');
} while ((n = tenth) != 0);
*s = (char)(*s + min_offset);
*p = '\0';
while (--p > s) {
swap = *s;
*s++ = *p;
*p = swap;
}
}

--
pete

Stefan Ram wrote:

> I was asking because some implementations of »itoa« start
> with something like:
>
> if( n < 0 ){ n = -n; *p++ = '-'; }
>
> , but then seem to fail sometimes for INT_MIN.
>
> I was wondering whether there is a portable implementation
> that will be correct for all int values.

void
itoa(int n, char *s)
{
if (0 > n) {
*s++ = '-';
*utoa_plus_one(-(n + 1), s) = '\0';
} else {
*utoa_plus_zero(n, s) = '\0';
}
}

static char *
utoa_plus_zero(unsigned n, char *s)
{
unsigned digit, tenth;

tenth = n / 10;
digit = n - 10 * tenth;
if (tenth != 0) {
s = utoa_plus_zero(tenth, s);
}
*s = (char)(digit + '0');
return s + 1;
}

static char *
utoa_plus_one(unsigned n, char *s)
{
unsigned digit, tenth;

tenth = n / 10;
digit = n - 10 * tenth;
if (digit == 9) {
if (tenth != 0) {
s = utoa_plus_one(tenth, s);
} else {
*s++ = '1';
}
*s = '0';
} else {
if (tenth != 0) {
s = utoa_plus_zero(tenth, s);
}
*s = (char)(digit + '1');
}
return s + 1;
}

--
pete

Stefan Ram wrote:
>
> Tim Rentsch <txr@alumni.caltech.edu> writes:

> >Note that for implementations where UINT_MAX == INT_MAX,

> I was asking because some implementations of »itoa« start
> with something like:
>
> if( n < 0 ){ n = -n; *p++ = '-'; }
>
> , but then seem to fail sometimes for INT_MIN.
>
> I was wondering whether there is a portable implementation
> that will be correct for all int values.
>
> One could set a flag when n == INT_MIN and then
> convert (n+1).

the special case is (-INT_MAX > n),
rather than (n == INT_MIN),
because of the (UINT_MAX == INT_MAX) possibility,
which was mentioned by Tim Rentsch.

--
pete

ram@zedat.fu-berlin.de (Stefan Ram) writes:

> Tim Rentsch <txr@alumni.caltech.edu> writes:
>>unsigned
>>unsigned_abs( int n ){
>> return n >= 0 ? n : -(n+1) + 1UL;
>>}
>>Note that for implementations where UINT_MAX == INT_MAX,
>>and where INT_MIN == -INT_MAX - 1 (which must be two's
>>complement), there is no unsigned int value that's right.
>>Under these conditions, unsigned_abs( INT_MIN ) gives zero.
>>In all other cases it gives the right value.
>
> I was asking because some implementations of >>itoa<< start
> with something like:
>
> if( n < 0 ){ n = -n; *p++ = '-'; }
>
> , but then seem to fail sometimes for INT_MIN.
>
> I was wondering whether there is a portable implementation
> that will be correct for all int values. [snip]

void
simple_itoa( int n, char *s ){
enum { D = 1 + CHAR_BIT*sizeof(int)/3 };
char buffer[D+1], *p = buffer + D;
*p = 0;

if( n < 0 ) *s++ = '-';
if( n > 0 ) n = -n;

while( n < -9 ){
int r = -(n+10)%10;
*--p = '0' + r;
n = (n+r)/10;
}
*--p = '0' + -n;

strcpy( s, p );
}


1. Works for all int values.

2. No casting or other types needed (and so no dependencies
on ranges of any other types).

3. No checks for "unusual" values.

4. Same results under both C90 and C99 (and C11) semantics.

5. (The expression computing a value for 'D' can be
improved, but the one here is probably good enough
in most cases.)


The code above may be used freely for any purpose subject
only to the condition that it not be claimed as original
work, ie, by anyone other than me. (And especially not
by any patent trolls out there...)