Databases
StackOverflow2013
Postsdbo
PO
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PO
    primarykey
    data
    text
    <p>Expanding on user71404's answer:</p> <pre><code>int f(unsigned x) { if (x &lt;= INT_MAX) return static_cast&lt;int&gt;(x); if (x &gt;= INT_MIN) return static_cast&lt;int&gt;(x - INT_MIN) + INT_MIN; throw x; // Or whatever else you like } </code></pre> <p>If <code>x &gt;= INT_MIN</code> (keep the promotion rules in mind, <code>INT_MIN</code> gets converted to <code>unsigned</code>), then <code>x - INT_MIN &lt;= INT_MAX</code>, so this won't have any overflow.</p> <p>If that is not obvious, take a look at the claim "If <code>x &gt;= -4u</code>, then <code>x + 4 &lt;= 3</code>.", and keep in mind that <code>INT_MAX</code> will be equal to at least the mathematical value of -INT_MIN - 1.</p> <p>On the most common systems, where <code>!(x &lt;= INT_MAX)</code> implies <code>x &gt;= INT_MIN</code>, the optimizer should be able (and on my system, is able) to remove the second check, determine that the two <code>return</code> statements can be compiled to the same code, and remove the first check too. Generated assembly listing:</p> <pre><code>__Z1fj: LFB6: .cfi_startproc movl 4(%esp), %eax ret .cfi_endproc </code></pre> <p>The hypothetical implementation in your question:</p> <ul> <li>INT_MAX equals 32767</li> <li>INT_MIN equals -2<sup>32</sup> + 32768</li> </ul> <p>is not possible, so does not need special consideration. <code>INT_MIN</code> will be equal to either <code>-INT_MAX</code>, or to <code>-INT_MAX - 1</code>. This follows from C's representation of integer types (6.2.6.2), which requires <code>n</code> 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 / <code>-INT_MAX - 1</code>. C++ doesn't allow any integer representations beyond what C allows.</p> <p><em><strong>Update</em></strong>: Microsoft's compiler apparently does not notice that <code>x &gt; 10</code> and <code>x &gt;= 11</code> test the same thing. It only generates the desired code if <code>x &gt;= INT_MIN</code> is replaced with <code>x &gt; INT_MIN - 1u</code>, which it can detect as the negation of <code>x &lt;= INT_MAX</code> (on this platform).</p> <p>[Update from questioner (Nemo), elaborating on our discussion below]</p> <p>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.</p> <p>Let's start with C++11, section 18.3.3:</p> <blockquote> <p>Table 31 describes the header <code>&lt;climits&gt;</code>.</p> <p>...</p> <p>The contents are the same as the Standard C library header <code>&lt;limits.h&gt;</code>.</p> </blockquote> <p>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.</p> <p>Since C++11 inherits the <code>&lt;climits&gt;</code> 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.)</p> <p>C++03/C++98 is trickier. It uses the same wording to inherit <code>&lt;climits&gt;</code> from "Standard C", but now "Standard C" means C89/C90.</p> <p>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):</p> <blockquote> <p>The representations of integral types shall define values by use of a pure binary numeration system.(44) [<em>Example</em>: this International Standard permits 2’s complement, 1’s complement and signed magnitude representations for integral types.]</p> </blockquote> <p>Footnote (44) defines "pure binary numeration system":</p> <blockquote> <p>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.</p> </blockquote> <p>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<sup>n-1</sup> (twos complement) or -(2<sup>n-1</sup>-1) (ones complement). But there is no value for the high bit that results in sign/magnitude.</p> <p>Anyway, my "hypothetical implementation" does not qualify as "pure binary" under this definition, so it is ruled out.</p> <p>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<sup>n-1</sup>-1), why not -(2<sup>n-1</sup>-2)? etc.)</p> <p>So, let's imagine a signed integer representation that assigns a wacky value to the "sign" bit. </p> <p>A small positive value for the sign bit would result in a positive range for <code>int</code> (possibly as large as <code>unsigned</code>), and hvd's code handles that just fine.</p> <p>A huge positive value for the sign bit would result in <code>int</code> having a maximum larger than <code>unsigned</code>, which is is forbidden.</p> <p>A huge negative value for the sign bit would result in <code>int</code> representing a non-contiguous range of values, and other wording in the spec rules that out.</p> <p>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<sup>31</sup>-1 and INT_MIN would be -37?</p> <p>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 <em>only</em> integer that might have two representations. So I think this new hypothetical is allowed by the spec.</p> <p>Indeed, any negative value from -1 down to <code>-INT_MAX-1</code> appears to be permissible as a value for the "sign bit", but nothing smaller (lest the range be non-contiguous). In other words, <code>INT_MIN</code> might be anything from <code>-INT_MAX-1</code> to -1.</p> <p>Now, guess what? For the second cast in hvd's code to avoid implementation-defined behavior, we just need <code>x - (unsigned)INT_MIN</code> less than or equal to <code>INT_MAX</code>. We just showed <code>INT_MIN</code> is at least <code>-INT_MAX-1</code>. Obviously, <code>x</code> is at most <code>UINT_MAX</code>. Casting a negative number to unsigned is the same as adding <code>UINT_MAX+1</code>. Put it all together:</p> <pre><code>x - (unsigned)INT_MIN &lt;= INT_MAX </code></pre> <p>if and only if</p> <pre><code>UINT_MAX - (INT_MIN + UINT_MAX + 1) &lt;= INT_MAX -INT_MIN-1 &lt;= INT_MAX -INT_MIN &lt;= INT_MAX+1 INT_MIN &gt;= -INT_MAX-1 </code></pre> <p>That last is what we just showed, so even in this perverse case, the code actually works.</p> <p>That exhausts all of the possibilities, thus ending this extremely academic exercise.</p> <p>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 <code>&lt;limits.h&gt;</code> from C99. But even C++11 retains the self-contradictory "pure binary representation" wording...</p>
    singulars
    1. This table or related slice is empty.
    1. POEfficient unsigned-to-signed cast avoiding implementation-defined behavior
      singulars
      1. PTQuestion
    1. PTAnswer
    1. USNemo
    1. UShvd
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. POEfficient unsigned-to-signed cast avoiding implementation-defined behavior
      singulars
      1. PTQuestion
    1. This table or related slice is empty.
    1. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    2. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    3. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTModeratorReview
    1. COQuestion updated. I am down-voting this answer (for now) to discourage others... I will un-down-vote later because answer is interesting. (Correct for C, but wrong for C++. I think.)
      singulars
      1. PO
      1. USNemo
    2. CO@Nemo The C standard applies to C++ in this case; at the very least, the values in `<limits.h>` are defined in the C++ standard as having the same meaning as in the C standard, so all of C's requirements for `INT_MIN` and `INT_MAX` are inherited in C++. You're correct that C++03 refers to C90, and C90 is vague about the allowed integer representations, but the C99 change (inherited at least via `<limits.h>` by C++11, hopefully also in a more straightforward way) to limit it to those three was one that codified existing practise: no other implementations existed.
      singulars
      1. PO
      1. UShvd
    3. COI agree that the meaning of `INT_MIN` etc. are inherited from C. But that does not mean the _values_ are. (Indeed, how could they, since every implementation is different?) Your inference that `INT_MIN` is within 1 of `-INT_MAX` depends on wording that simply does not appear in any C++ spec. So while C++ does inherit the semantic meaning of the macros, the spec does not provide (or inherit) the wording that supports your inference. This appears to be an oversight in the C++ spec that prevents a fully-conforming efficient unsigned-to-signed cast.
      singulars
      1. PO
      1. USNemo
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload