Alex Rivera | Logout

Efficient unsigned-to-signed cast avoiding implementation-defined behavior

Asked 2012-10-31T02:32:10.630
115

I want to define a function that takes an unsigned int as argument and returns an int congruent modulo UINT_MAX+1 to the argument.

A first attempt might look like this:

int unsigned_to_signed(unsigned n)
{
    return static_cast<int>(n);
}

But as any language lawyer knows, casting from unsigned to signed for values larger than INT_MAX is implementation-defined.

I want to implement this such that (a) it only relies on behavior mandated by the spec; and (b) it compiles into a no-op on any modern machine and optimizing compiler.

As for bizarre machines... If there is no signed int congruent modulo UINT_MAX+1 to the unsigned int, let's say I want to throw an exception. If there is more than one (I am not sure this is possible), let's say I want the largest one.

OK, second attempt:

int unsigned_to_signed(unsigned n)
{
    int int_n = static_cast<int>(n);

    if (n == static_cast<unsigned>(int_n))
        return int_n;

    // else do something long and complicated
}

I do not much care about the efficiency when I am not on a typical twos-complement system, since in my humble opinion that is unlikely. And if my code becomes a bottleneck on the omnipresent sign-magnitude systems of 2050, well, I bet someone can figure that out and optimize it then.

Now, this second attempt is pretty close to what I want. Although the cast to int is implementation-defined for some inputs, the cast back to unsigned is guaranteed by the standard to preserve the value modulo UINT_MAX+1. So the conditional does check exactly what I want, and it will compile into nothing on any system I am likely to encounter.

However... I am still casting to int without first checking whether it will invoke implementation-defined behavior. On some hypothetical system in 2050 it could do who-knows-what. So

c++ casting integer language-lawyer integer-overflow
Edit
Report

1 Answer

3

If x is our input...

If x > INT_MAX, we want to find a constant k such that 0 < x - k*INT_MAX < INT_MAX.

This is easy -- unsigned int k = x / INT_MAX;. Then, let unsigned int x2 = x - k*INT_MAX;

We can now cast x2 to int safely. Let int x3 = static_cast<int>(x2);

We now want to subtract something like UINT_MAX - k * INT_MAX + 1 from x3, if k > 0.

Now, on a 2s complement system, so long as x > INT_MAX, this works out to:

unsigned int k = x / INT_MAX;
x -= k*INT_MAX;
int r = int(x);
r += k*INT_MAX;
r -= UINT_MAX+1;

Note that UINT_MAX+1 is zero in C++ guaranteed, the conversion to int was a noop, and we subtracted k*INT_MAX then added it back on "the same value". So an acceptable optimizer should be able to erase all that tomfoolery!

That leaves the problem of x > INT_MAX or not. Well, we create 2 branches, one with x > INT_MAX, and one without. The one without does a strait cast, which the compiler optimizes to a noop. The one with ... does a noop after the optimizer is done. The smart optimizer realizes both branches to the same thing, and drops the branch.

Issues: if UINT_MAX is really large relative to INT_MAX, the above might not work. I am assuming that k*INT_MAX <= UINT_MAX+1 implicitly.

We could probably attack this with some enums like:

enum { divisor = UINT_MAX/INT_MAX, remainder = UINT_MAX-divisor*INT_MAX };

which work out to 2 and 1 on a 2s complement system I believe (are we guaranteed for that math to work? That's tricky...), and do logic based on these that easily optimize away on non-2s complement syst

answered 2012-10-31T03:26:47.383

Your Answer