Unary minus and signed-to-unsigned conversion

Asked 2010-12-27T00:55:43.730

Is this always technically correct:

unsigned abs(int n)
{
    if (n >= 0) {
        return n;
    } else {
        return -n;
    }
}

It seems to me that here if -INT_MIN > INT_MAX, the "-n" expression could overflow when n == INT_MIN, since -INT_MIN is outside the bounds. But on my compiler this seems to work ok... is this an implementation detail or a behaviour that can be relied upon?

Longer version

A bit of context: I'm writing a C++ wrapper for the GMP integer type (mpz_t) and taking inspiration for the existing GMP C++ wrapper (called mpz_class). When handling addition of mpz_t with signed integers there is code like this:

static void eval(mpz_ptr z, signed long int l, mpz_srcptr w)
{
  if (l >= 0)
    mpz_add_ui(z, w, l);
  else
    mpz_sub_ui(z, w, -l);
}

In other words, if the signed integer is positive, add it using the routine of unsigned addition, if the signed integer is negative add it using the routine of unsigned subtraction. Both *_ui routines take unsigned long as last arguments. Is the expression

-l

at risk of overflowing?

c++ c

Edit Report

4 Answers

If you want to avoid the overflow, you should first cast n to an unsigned int and then apply the unary minus to it.

unsigned abs(int n) {
  if (n >= 0)
    return n;
  return -((unsigned)n);
}

In your original code the negation happens before the type conversion, so the behavior is undefined if n < -INT_MAX.

When negating an unsigned expression, there will never be overflow. Instead the result will be modulo 2^x, for the appropriate value of x.

answered 2010-12-27T01:31:33.190

Most computers today use a two complement number scale, which means the negative part is one larger than the positive, for example from -128 to 127. That means if you can represent the positive number the negative number you can represent the negative number without worry.

answered 2010-12-27T01:00:16.827

Maybe it could cope with the symmetrical range of 2's-complement numbers:

#include <limits.h>

unsigned int abs(int n){

  unsigned int m;

  if(n == INT_MIN)
    m = INT_MAX + 1UL;
  else if(n < 0)
    m = -n;
  else 
    m = n;

  return m;
}

answered 2010-12-27T02:10:37.917

-1

Very good question, which exposes the differences between C89, C99 and C++. So this is some commentary on these Standards.

In C89, where n is an int:

(unsigned)n

is not well defined for all n: there's no restriction on the conversion of signed or unsigned int except that the representation of a non-negative signed int is identical to that of an unsigned int of the same value, provided that value is representable.

This was considered a defect, and in C99, unfortunately there is a faulty attempt to restrict the encoding to two's complement, one's complement, or signed magnitude with the same number of bits. Unfortunately the C committee didn't have much mathematical knowledge and completely botched the specification: on the one hand it is ill-formed due to circular definition and therefore non-normative, and on the other hand, if you excuse this fault, it is a gross overconstraint, which, for example, excludes a BCD representation (used in C on old IBM mainframes), and also allows the programmer to hack the value of an integer by fiddling bits of the representation (which is very bad).

C++ went to some trouble to provide a better specification, however it suffers the same circular definition fault.

Roughly speaking, the representation of a value v is an array of unsigned char with sizeof(v) elements. An unsigned char has a power of two number of elements, and is required to be big enough to ensure it faithfully encodes any aliased data structure. The number of bits in an unsigned char is well defined as the binary log of the number of values representable.

The number of bits of any unsigned value is similarly well defined if it has a power of two number of values from 0 to 2^n-1, by via the canonical positional encoding scheme.

Unfortunately, the committee wanted to ask if there were any "holes" in the representation. For example could you have a 31 bit integer on a

answered 2010-12-27T06:35:19.337

Unary minus and signed-to-unsigned conversion

4 Answers

Your Answer