Efficient Unsigned-To-Signed Cast Avoiding Implementation-Defined Behavior

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

Expanding on user71404's answer:

int f(unsigned x)
{
    if (x <= INT_MAX)
        return static_cast<int>(x);

    if (x >= INT_MIN)
        return static_cast<int>(x - INT_MIN) + INT_MIN;

    throw x; // Or whatever else you like
}

If x >= INT_MIN (keep the promotion rules in mind, INT_MIN gets converted to unsigned), then x - INT_MIN <= INT_MAX, so this won't have any overflow.

If that is not obvious, take a look at the claim "If x >= -4u, then x + 4 <= 3.", and keep in mind that INT_MAX will be equal to at least the mathematical value of -INT_MIN - 1.

On the most common systems, where !(x <= INT_MAX) implies x >= INT_MIN, the optimizer should be able (and on my system, is able) to remove the second check, determine that the two return statements can be compiled to the same code, and remove the first check too. Generated assembly listing:

__Z1fj:
LFB6:
    .cfi_startproc
    movl    4(%esp), %eax
    ret
    .cfi_endproc

The hypothetical implementation in your question:

• INT_MAX equals 32767
• INT_MIN equals -2³² + 32768

is not possible, so does not need special consideration. INT_MIN will be equal to either -INT_MAX, or to -INT_MAX - 1. This follows from C's representation of integer types (6.2.6.2), which requires n bits to be value bits, one bit to be a sign bit, and only allows one single trap representation (not including representations that are invalid because of padding bits), namely the one that would otherwise represent negative zero / -INT_MAX - 1. C++ doesn't allow any integer representations beyond what C allows.

Update: Microsoft's compiler apparently does not notice that x > 10 and x >= 11 test the same thing. It only generates the desired code if x >= INT_MIN is replaced with x > INT_MIN - 1u, which it can detect as the negation of x <= INT_MAX (on this platform).

[Update from questioner (Nemo), elaborating on our discussion below]

I now believe this answer works in all cases, but for complicated reasons. I am likely to award the bounty to this solution, but I want to capture all the gory details in case anybody cares.

Let's start with C++11, section 18.3.3:

Table 31 describes the header <climits>.

...

The contents are the same as the Standard C library header <limits.h>.

Here, "Standard C" means C99, whose specification severely constrains the representation of signed integers. They are just like unsigned integers, but with one bit dedicated to "sign" and zero or more bits dedicated to "padding". The padding bits do not contribute to the value of the integer, and the sign bit contributes only as twos-complement, ones-complement, or sign-magnitude.

Since C++11 inherits the <climits> macros from C99, INT_MIN is either -INT_MAX or -INT_MAX-1, and hvd's code is guaranteed to work. (Note that, due to the padding, INT_MAX could be much less than UINT_MAX/2... But thanks to the way signed->unsigned casts work, this answer handles that fine.)

C++03/C++98 is trickier. It uses the same wording to inherit <climits> from "Standard C", but now "Standard C" means C89/C90.

All of these -- C++98, C++03, C89/C90 -- have the wording I give in my question, but also include this (C++03 section 3.9.1 paragraph 7):

The representations of integral types shall define values by use of a
pure binary numeration system.(44) [Example: this International
Standard permits 2’s complement, 1’s complement and signed magnitude
representations for integral types.]

Footnote (44) defines "pure binary numeration system":

A positional representation for integers that uses the binary digits 0
and 1, in which the values represented by successive bits are
additive, begin with 1, and are multiplied by successive integral
power of 2, except perhaps for the bit with the highest position.

What is interesting about this wording is that it contradicts itself, because the definition of "pure binary numeration system" does not permit a sign/magnitude representation! It does allow the high bit to have, say, the value -2^n-1 (twos complement) or -(2^n-1-1) (ones complement). But there is no value for the high bit that results in sign/magnitude.

Anyway, my "hypothetical implementation" does not qualify as "pure binary" under this definition, so it is ruled out.

However, the fact that the high bit is special means we can imagine it contributing any value at all: A small positive value, huge positive value, small negative value, or huge negative value. (If the sign bit can contribute -(2^n-1-1), why not -(2^n-1-2)? etc.)

So, let's imagine a signed integer representation that assigns a wacky value to the "sign" bit.

A small positive value for the sign bit would result in a positive range for int (possibly as large as unsigned), and hvd's code handles that just fine.

A huge positive value for the sign bit would result in int having a maximum larger than unsigned, which is is forbidden.

A huge negative value for the sign bit would result in int representing a non-contiguous range of values, and other wording in the spec rules that out.

Finally, how about a sign bit that contributes a small negative quantity? Could we have a 1 in the "sign bit" contribute, say, -37 to the value of the int? So then INT_MAX would be (say) 2³¹-1 and INT_MIN would be -37?

This would result in some numbers having two representations... But ones-complement gives two representations to zero, and that is allowed according to the "Example". Nowhere does the spec say that zero is the only integer that might have two representations. So I think this new hypothetical is allowed by the spec.

Indeed, any negative value from -1 down to -INT_MAX-1 appears to be permissible as a value for the "sign bit", but nothing smaller (lest the range be non-contiguous). In other words, INT_MIN might be anything from -INT_MAX-1 to -1.

Now, guess what? For the second cast in hvd's code to avoid implementation-defined behavior, we just need x - (unsigned)INT_MIN less than or equal to INT_MAX. We just showed INT_MIN is at least -INT_MAX-1. Obviously, x is at most UINT_MAX. Casting a negative number to unsigned is the same as adding UINT_MAX+1. Put it all together:

x - (unsigned)INT_MIN <= INT_MAX

if and only if

UINT_MAX - (INT_MIN + UINT_MAX + 1) <= INT_MAX
-INT_MIN-1 <= INT_MAX
-INT_MIN <= INT_MAX+1
INT_MIN >= -INT_MAX-1

That last is what we just showed, so even in this perverse case, the code actually works.

That exhausts all of the possibilities, thus ending this extremely academic exercise.

Bottom line: There is some seriously under-specified behavior for signed integers in C89/C90 that got inherited by C++98/C++03. It is fixed in C99, and C++11 indirectly inherits the fix by incorporating <limits.h> from C99. But even C++11 retains the self-contradictory "pure binary representation" wording...

Why casting unsigned to signed directly in C gives correct result?

Your claim that ...

In C, signed integer and unsigned integer are stored differently in memory

... is largely wrong. The standard instead specifies:

For signed integer types, the bits of the object representation shall be divided into three groups: value bits, padding bits, and the sign bit. There need not be any padding bits; signed char shall not have any padding bits. There shall be exactly one sign bit. Each bit that is a value bit shall have the same value as the same bit in the object representation of the corresponding unsigned type (if there are M value bits in the signed type and N in the unsigned type, then M <= N ). If the sign bit is zero, it shall not affect the resulting value.

(C2011 6.2.6.2/2; emphasis added)

Thus, although the representation of a signed integer type and its corresponding unsigned integer type (which have the same size) must differ at least in that former has a sign bit and the latter does not, most bits of the representations in fact correspond exactly. The standard requires it. Small(ish), non-negative integers will be represented identically in corresponding signed and unsigned integer types.

Additionally, some of the comments raised the matter of the "strict aliasing rule", which is paragraph 6.5/7 of the standard. It forbids accessing an object of one type via an lvalue of a different type, as your code does, but it allows some notable exceptions. One of the exceptions is that you may access an object via an lvalue whose type is

• a type that is the signed or unsigned type corresponding to the effective type of the object,

That is in fact what your code does, so there is no strict-aliasing violation there.

Cast unsigned to signed and back

No, you don't have such guarantee: [conv.integral]

2 If the destination type is unsigned, the resulting value is the least unsigned integer congruent to the source
integer (modulo 2^n where n is the number of bits used to represent the unsigned type). [ Note: In a two’s
complement representation, this conversion is conceptual and there is no change in the bit pattern (if there is
no truncation). —end note ]

3 If the destination type is signed, the value is unchanged if it can be represented in the destination type;
otherwise, the value is implementation-defined.

Conversion to signed type behavior when out of range

Neither of these quotes are meant to say that the original value is taken, the modulo operation applied, and the result used as result of the conversion.

Instead they are meant to say that out of all values v representable in the destination type, the (unique) one for which the mathematical equality

s + m * 2^n = v

holds for some integer m, with s the source value, is chosen. It is said that s and v are congruent modulo 2^n if they satisfy this condition or sometimes also that they are equal modulo 2^n.

For s = 255 with signed target of width 8, 255 is not representable, but -1 is and v = -1 satisfies the equation with m = -1.

C++ Converting unsigned to signed integer portability

Since C++20 finally got rid of ones' complement and sign-magnitude integers, conversion between signed and unsigned integers is well-defined and reversible. All standard integer types are now 2's complement and conversion between signed and unsigned does not alter any bits in the representation.

For versions of C++ prior to C++20, the original answer still applies. I'm leaving it as a historical remnant.

---

Conversion of an unsigned integer to a signed integer where the unsigned value is outside of the range of the signed type is implementation-defined. You cannot count on being able to round-trip a negative integer to unsigned and then back to signed. [1]

C++ standard, [conv.integral], § 4.7/3:

If the destination type is signed, the value is unchanged if it can be represented in the destination type (and bit-field width); otherwise, the value is implementation-defined.

[1] It seems likely that it will work, but there are no guarantees.

Unsigned/Signed Integer Addition with Casting

With unsigned types, addition is guaranteed to wrap around: if you add 1 to the maximum uint64_t, you get 0.

With signed types, in both C and C++, wraparound is undefined behavior: anything could happen, and in practice the compiler can do things you don't expect if you have optimization turned on.

So no, this is not guaranteed by the standard.

However, many compilers give an option to, as an extension to the standard, guarantee wrapped behavior for signed types, in which case the answer is yes. For example, see -fwrapv of GCC and Clang.

---

Related Topics