Efficient unsigned crane that eliminates implementation-defined behavior

Question

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

The first attempt might look like this:

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

But, as any lawyer knows, casting from unsigned to signed for values ​​greater than INT_MAX is determined by the implementation.

I want to implement this so that (a) it relies only on the behavior specified by the specification; and (b) it compiles into no-op on any modern machine and optimizes the compiler.

As for fancy cars ... If there is no signed int congruent modulo UINT_MAX + 1 in unsigned int, let's say I want to throw an exception. If there are several (I'm not sure if this is possible), let's say I want the biggest.

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 don’t really care about efficiency when I’m not in a typical dual supplement system, since in my humble opinion this is unlikely. And if my code becomes a bottleneck in the ubiquitous systems of the iconic magnitude of 2050, I would say that someone can understand this and optimize it then.

Now this second attempt is pretty close to what I want. Although casting to int is determined by the implementation for some inputs, returning to unsigned guaranteed by the standard for storing the value modulo UINT_MAX + 1. Thus, the condition really checks what I want and it compiles to nothing on any system with which I probably I will face.

However ... I still resort to int without first checking to see if it will trigger the behavior defined by the implementation. In a hypothetical system in 2050, he could have done, who-knows-what. So let me say that I want to avoid this.

Question: What should my “third attempt” look like?

To repeat, I want:

• Pass from unsigned int to signed int
• Save the value of mod UINT_MAX + 1
• Call only standard behavior.
• Compiling in no-op on a typical machine with two additional components with an optimizing compiler

[Update]

Let me give an example to show why this is not a trivial question.

Consider a hypothetical C ++ implementation with the following properties:

• sizeof(int) is 4
• sizeof(unsigned) is 4
• INT_MAX equals 32767
• INT_MIN is -2 ³² + 32768
• UINT_MAX is 2 ³² - 1
• Arithmetic to int modulo 2 ³² (in the range of INT_MIN via INT_MAX )
• std::numeric_limits<int>::is_modulo true
• Unsigned n casting in int stores the value for 0 <= n <= 32767 and returns zero otherwise

In this hypothetical implementation, for each unsigned value, there is exactly one int value (mod UINT_MAX + 1). Therefore, my question will be clearly defined.

I claim that this hypothetical implementation in C ++ fully complies with the specifications C ++ 98, C ++ 03 and C ++ 11. I admit that I did not remember every word of all ... But I believe that I carefully read relevant sections. Therefore, if you want me to accept your answer, you must either (a) specify a specification that excludes this hypothetical implementation, or (b) process it correctly.

Indeed, the correct answer should handle every hypothetical implementation permitted by the standard. This is what “causes only standard behavior” means, by definition.

By the way, note that std::numeric_limits<int>::is_modulo is completely useless here for several reasons. First, it can be true , even if unsigned casts do not work for large unsigned values. For another, this can be true even in systems with one complement or sign value, if arithmetic is simply modulo the entire integer range. And so on. If your answer depends on is_modulo , this is wrong.

[Update 2]

hvd answer taught me something: my hypothetical C ++ implementation for integers is not allowed by modern C. Standards C99 and C11 are very specific with respect to the representation of signed integers; indeed, they allow only double additions, single additions and sign values ​​(section 6.2.6.2, paragraph (2);).

But C ++ is not C. As it turns out, this fact lies at the very heart of my question.

The original C ++ 98 standard was based on the much older C89, which states (section 3.1.2.5):

For each of the signed integer types, there is a corresponding (but different) unsigned integer type (indicated by the unsigned keyword) that uses the same storage capacity (including the information sign) and has the same alignment requirements. A range of non-negative values ​​of a signed integer type are subbands of the corresponding unsigned integer type, and the same value representation is the same in each type.

C89 does not say anything that has only one bit sign or allows only binary complement / unit / digit value.

The C ++ 98 standard adopted this language almost verbatim (section 3.9.1 (3)):

For each of the signed integer types, there is a corresponding (but different) unsigned integer type: " unsigned char ", " unsigned short int ", " unsigned int " and " unsigned long int ", each of which occupies the same storage capacity and has the same alignment of the requirement (3.9) as the corresponding signed integer type; that each character of an integer type has the same object representation as its corresponding unsigned integer type. The range of non-negative values ​​of the signed integer type are subbands of the corresponding unsigned integer type and the representation of the values ​​of each corresponding type of the signed / unsigned type must be the same.

The C ++ 03 standard uses an almost identical language, like C ++ 11.

No standard C ++ specification limits its signed integer representations to any C spec, as far as I can tell. And there is nothing that would mean a single sign or something like that. All this suggests that non-negative signed integers must be a subrange of the corresponding unsigned.

So, again I say that INT_MAX = 32767 with INT_MIN = -2 ³² +32768 is allowed. Unless your answer suggests otherwise, this is not true unless you have specified a C ++ standard proving that I'm wrong.

Answer 1

User71404 answer extension:

 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 (follow the promotion rules, INT_MIN converted to unsigned ), then x - INT_MIN <= INT_MAX , so this will not overflow.

If this is not obvious, 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 math value -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, able) to remove the second check, determine that two return can be compiled for the same code, and also remove the first check. List of assembled assemblies:

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

Hypothetical implementation in your question:

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

impossible, therefore, does not require special consideration. INT_MIN will be either -INT_MAX or -INT_MAX - 1 . This follows from the representation C of integer types (6.2.6.2), for which bit n must be value bits, one bit must be a signed bit and allows only one trap representation (not counting invalid representations due to filling bits), namely the one that otherwise it would represent negative zero / -INT_MAX - 1 . C ++ does not allow any integer representations other than what C allows.

Refresh . The Microsoft compiler does not seem to notice that the tags x > 10 and x >= 11 are checking the same thing. It only generates the desired code if x >= INT_MIN is replaced by x > INT_MIN - 1u , which it can detect as negation x <= INT_MAX (on this platform).

[Update from the survey (Nemo), in which we discuss below]

Now I believe that this answer works in all cases, but for complex reasons. I will most likely award a reward for this decision, but I want to capture all the gory details in case someone cares.

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

Table 31 describes the <climits> header.

...

The content is the same as the title of the standard C library <limits.h> .

Here, “Standard C” means C99, the specification of which severely restricts the representation of signed integers. They look like unsigned integers, but with one bit intended for the “sign”, and zero or more bits intended for the “fill”. The padding bits do not contribute to the value of the integer, and the signed bit only contributes as a double padding, single padding or signed value.

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

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

All of them - 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):

Integral type representations must define values ​​using a pure binary numbering system. (44) [Example: this International Standard allows for the addition of 2s, the addition of 1s and the signature of the representation for integral types.]

Footnote (44) defines a “pure binary numbering system”:

A positional representation for integers that uses the binary digits 0 and 1, in which the values ​​represented by the successive bits are additive, start with 1 and multiply by the power integral 2, with the possible exception of the bit with the highest position.

What is interesting in this formulation is that it contradicts itself, because the definition of a "pure binary numbering system" does not allow the representation of a sign / quantity! This allows a high bit to have, say, a value of -2 ^n-1 (two additions) or - (2 ^n-1 -1) (one addition), but for a large bit there is no value that leads to a sign / value.

In any case, my “hypothetical implementation” does not qualify as “pure binary” in accordance with this definition, therefore it is excluded.

However, the fact that the high bit is a special tool, we can imagine that it brings any value at all: a small positive value, a huge positive value, a small negative value or a huge negative value. (If the sign bit can contribute - (2 ^n-1 -1), why not - (2 ^n-1 -2)? And so on.)

So, imagine an integer representation with a sign that assigns an empty value to the "sign" bit.

A small positive value for the sign bit will result in a positive range for the int (possibly as large as unsigned ), and the hvd code handles this simply.

A huge positive value for the sign bit will cause int have a maximum exceeding unsigned , which is prohibited.

A huge negative value for the sign bit will lead to the fact that int will be an non-contiguous range of values ​​and a different formulation in the specification rules.

Finally, what about the sign bit, which introduces a small negative value? Can we have 1 in the "sign bit", for example, to add the value -37 to the value of int? So, INT_MAX will (say) 2 ³¹ -1, and INT_MIN will be -37?

This will lead to some numbers having two representations ... But a single complement gives two representations to zero, and this is allowed by the "example". Nowhere does the specification say that zero is the only integer that can have two representations. Therefore, I think that this hypothesis is allowed by the specification.

Indeed, any negative value from -1 to -INT_MAX-1 appears to be valid as a value for the "sign bit", but nothing less (so that the range is not continuous). In other words, INT_MIN can be anything: from -INT_MAX-1 to -1.

Now guess what? For the second cast in the hvd code, to avoid the behavior defined during implementation, we just need x - (unsigned)INT_MIN less than or equal to INT_MAX . We just showed that INT_MIN at least -INT_MAX-1 . Obviously, x does not exceed UINT_MAX . Dropping a negative unsigned number is the same as adding UINT_MAX+1 . Combine all of this:

 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 

The last thing we just showed, so even in this flawed case, the code really works.

This exhausts all possibilities, thereby ending this extremely academic exercise.

Bottom line. There is some seriously undefined behavior for signed integers in C89 / C90 that were inherited from C ++ 98 / C ++ 03. It is fixed in C99, and C ++ 11 indirectly inherits the correction by including <limits.h> from C99. But even C ++ 11 preserves the very contradictory wording of the "pure binary representation" ...

Answer 2

This code relies only on the behavior specified by the specification, so requirement (a) is easily met:

 int unsigned_to_signed(unsigned n) { int result = INT_MAX; if (n > INT_MAX && n < INT_MIN) throw runtime_error("no signed int for this number"); for (unsigned i = INT_MAX; i != n; --i) --result; return result; } 

This is not so simple with requirement (b). This compiles in no-op with gcc 4.6.3 (-Os, -O2, -O3) and with clang 3.0 (-Os, -O, -O2, -O3). Intel 12.1.0 refuses to optimize this. And I have no information about Visual C.

Answer 3

You can explicitly tell the compiler what you want to do:

 int unsigned_to_signed(unsigned n) { if (n > INT_MAX) { if (n <= UINT_MAX + INT_MIN) { throw "no result"; } return static_cast<int>(n + INT_MIN) - (UINT_MAX + INT_MIN + 1); } else { return static_cast<int>(n); } } 

Compiles with gcc 4.7.2 for x86_64-linux ( g++ -O -S test.cpp ) before

 _Z18unsigned_to_signedj: movl %edi, %eax ret 

Answer 4

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 .

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

Now we can safely use x2 to int . Let int x3 = static_cast<int>(x2);

Now we want to subtract something like UINT_MAX - k * INT_MAX + 1 from x3 if k > 0 .

Now, in the 2s add-on system, while x > INT_MAX , this works:

 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 ++, the conversion to int was noop, and we subtracted k*INT_MAX , and then added it back to "the same value". Thus, an acceptable optimizer should be able to erase all this nonsense!

This leaves the problem x > INT_MAX or not. Well, we create 2 branches, one with x > INT_MAX , and one without it. One who does not have the simplest throw, which the compiler optimizes for noop. Anyone who has ... does a noop after the optimizer is done. The intelligent optimizer implements both branches in the same thing and discards the branch.

Problems: if UINT_MAX really large relative to INT_MAX , the above may not work. I assume that k*INT_MAX <= UINT_MAX+1 implicit.

We could attack this with some enumerations like:

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

which work up to 2 and 1 in the 2s complement system, I suppose (we guarantee that this math works? Is it difficult ...), and based on logic that is easily optimized on non-2s complement systems ...

This also opens up an exception case. This is only possible if UINT_MAX is much larger (INT_MIN-INT_MAX), so you can put your exception code in the if block by asking just such a question, and it will not slow you down in a traditional system.

I'm not quite sure how to build these compile-time constants to handle this correctly.

Answer 5

std::numeric_limits<int>::is_modulo - compile time constant. therefore, you can use it to specialize templates. The problem is solved, at least if the compiler plays along with inlining.

 #include <limits> #include <stdexcept> #include <string> #ifdef TESTING_SF bool const testing_sf = true; #else bool const testing_sf = false; #endif // C++ "extensions" namespace cppx { using std::runtime_error; using std::string; inline bool hopefully( bool const c ) { return c; } inline bool throw_x( string const& s ) { throw runtime_error( s ); } } // namespace cppx // C++ "portability perversions" namespace cppp { using cppx::hopefully; using cppx::throw_x; using std::numeric_limits; namespace detail { template< bool isTwosComplement > int signed_from( unsigned const n ) { if( n <= unsigned( numeric_limits<int>::max() ) ) { return static_cast<int>( n ); } unsigned const u_max = unsigned( -1 ); unsigned const u_half = u_max/2 + 1; if( n == u_half ) { throw_x( "signed_from: unsupported value (negative max)" ); } int const i_quarter = static_cast<int>( u_half/2 ); int const int_n1 = static_cast<int>( n - u_half ); int const int_n2 = int_n1 - i_quarter; int const int_n3 = int_n2 - i_quarter; hopefully( n == static_cast<unsigned>( int_n3 ) ) || throw_x( "signed_from: range error" ); return int_n3; } template<> inline int signed_from<true>( unsigned const n ) { return static_cast<int>( n ); } } // namespace detail inline int signed_from( unsigned const n ) { bool const is_modulo = numeric_limits< int >::is_modulo; return detail::signed_from< is_modulo && !testing_sf >( n ); } } // namespace cppp #include <iostream> using namespace std; int main() { int const x = cppp::signed_from( -42u ); wcout << x << endl; } 

---

EDIT . , (, , Unisys Clearpath). , -2 ^{n -1} n - int , (.. Clearpath). (.. 1 - ).

Answer 6

, int , INT_MIN INT_MAX .

& le; climits & ge; Headline

Answer 7

My money is using memcpy. Any worthy compiler knows how to optimize it:

 #include <stdio.h> #include <memory.h> #include <limits.h> static inline int unsigned_to_signed(unsigned n) { int result; memcpy( &result, &n, sizeof(result)); return result; } int main(int argc, const char * argv[]) { unsigned int x = UINT_MAX - 1; int xx = unsigned_to_signed(x); return xx; } 

For me (Xcode 8.3.2, Apple LLVM 8.1, -O3), which produces:

 _main: ## @main Lfunc_begin0: .loc 1 21 0 ## /Users/Someone/main.c:21:0 .cfi_startproc ## BB#0: pushq %rbp Ltmp0: .cfi_def_cfa_offset 16 Ltmp1: .cfi_offset %rbp, -16 movq %rsp, %rbp Ltmp2: .cfi_def_cfa_register %rbp ##DEBUG_VALUE: main:argc <- %EDI ##DEBUG_VALUE: main:argv <- %RSI Ltmp3: ##DEBUG_VALUE: main:x <- 2147483646 ##DEBUG_VALUE: main:xx <- 2147483646 .loc 1 24 5 prologue_end ## /Users/Someone/main.c:24:5 movl $-2, %eax popq %rbp retq Ltmp4: Lfunc_end0: .cfi_endproc 

Answer 8

It is completely standard compatible and will compile in no-op on MSVC / gcc.

 int unsigned_to_signed(unsigned int n) { union UltimateCast { unsigned int In; int Out; } cast; cast.In = n; return cast.Out; } 

For the calling code:

 volatile unsigned int i = 32167; int main() { return unsigned_to_signed( i ); } 

We will have this build output (g ++ -O3 -S):

 __Z18unsigned_to_signedj: movl 4(%esp), %eax ret _main: pushl %ebp movl %esp, %ebp andl $-16, %esp call ___main movl _i, %eax leave ret .globl _i .data .align 4 _i: .long 32167 

And the announcement unsigned_to_signed()as inlinegives:

 _main: pushl %ebp movl %esp, %ebp andl $-16, %esp call ___main movl _i, %eax leave ret .globl _i .data .align 4 _i: .long 32167 

This is pretty neat code.