12 ms·
Signed Integers Are Two’s Complement
- scott_s 8y agoIn April, the author of this proposal said on Twitter that the C++ standards committee agreed to this proposal for C++20: https://twitter.com/jfbastien/status/989242576598327296?lang=en https://twitter.com/jfbastien/status/989242576598327296?lang...
- fred256 8y agoI'm curious why some old architectures didn't use two's complement for signed numbers. What advantage did one's complement or signed magnitude have over two's complement?
- sunfish 8y agoTwo's complement has the bizarre property of being asymmetric about zero. So things like `abs` can overflow, among several other oddities. It's not unambiguously better.
- 0xcde4c3db 8y agoIt can be useful to distinguish between positive and negative zero in some cases, for example when dealing with values that have been rounded to zero or limits approaching zero.
- lopmotr 8y agoWas that ever really a reason for signed magnitude, or did people just make use of the 2nd representation of zero because because it was available and they couldn't be bothered putting that information in another variable or using floating point or fixed point, or anything else that would have achieved the same result?
- userbinator 8y agoI have a feeling signed-magnitude predates binary and complement arithmetic --- it is, after all, the "natural" way humans work with numbers. A lot of the early non-binary computers used some form of sign-magnitude, all the way back to punch card formats: https://en.wikipedia.org/wiki/Signed_overpunch https://en.wikipedia.org/wiki/Signed_overpunch On the other hand (no pun intended), early mechanical (decimal) manual adding machines made use of complement arithmetic too: https://en.wikipedia.org/wiki/Comptometer https://en.wikipedia.org/wiki/Comptometer https://en.wikipedia.org/wiki/Method_of_complements https://en.wikipedia.org/wiki/Method_of_complements
- Phrodo_00 8y agoTIL about signed overpunch Except the "natural" way also recognizes a single zero with no sign, so it's still not accurately modeling that. If you wanted to model natural arithmetic accurately you'd need 2 bits for the sign (positive, negative, unsigned). At that point, all of single bit signed magnitude, and complements are compromises.
- Animats 8y agoBurroughs 5xxx and 6xxx machines used signed-magnitude. Burroughs had a unique numeric representation. Numbers were 48 bits. Sign, sign of exponent, exponent, mantissa, with the binary point at the low end. Integers were thus valid floating point numbers. The math operations would maintain a value as an integer, with a zero exponent, if possible. IEEE floating point also maintains integer values as integers until they don't fit, but the representation is not integer-like.
- 8y ago
- paulddraper 8y agoDon't forget negabinary! https://en.m.wikipedia.org/wiki/Negative_base https://en.m.wikipedia.org/wiki/Negative_base Negabinary operations are extremely simple and elegant. Like 2s complement and 1s complement, it suffers from asymmetry in its range, though even more so.
- evincarofautumn 8y agoI always felt like negative bases are just strange enough, yet just practical enough, that they almost could have arisen as a system of numbers in a natural language. For example, phrasing 11 as 191, “one more than 90 less than 100”, would be unusual for such a small number but definitely sounds “naturalistic”, like phrasing 1990 as “a thousand, a hundred less than a thousand, ten less than a hundred” in Roman numerals, 99 as “four-twenty ten-nine” in French, or 9 as “five four” in Khmer.
- garmaine 8y agoIn addition to what's mentioned in the already great sibling comments, it's worth noting that IEEE floating point is signed-magnitude.
- jovial_cavalier 8y agoIs there a good way to represent floating points in order to do complement arithmetic?
- garmaine 8y agoYes, see JavaScript: https://www.w3schools.com/js/js_numbers.asp https://www.w3schools.com/js/js_numbers.asp
- hamiltonkibbe 8y agoIf you know a bit about the range you need to support you could use a fixed point representation
- userbinator 8y agoSign-magnitude for the significand, and offset-binary for the exponent. The reason for this odd combination is probably historical.
- p1mrx 8y agoIt doesn't seem odd to me. When describing things in nature, (+x, -x) tend to have more symmetry than (x, 1/x).
- sasaf5 8y agoWith one's complement it is easier to multiply by minus one: just invert all bits. It is also symmetrical around the zero, so sequences of random numbers will truly tend to average to zero.
- CJefferson 8y agoThe big one (for me) is that it's really annoying having one more negative value than positive value. Most software doesn't handle this properly, they don't realise abs doesn't always return a positive number (as abs(INT_MIN)=INT_MIN), and many other similar problems. In an ideal world, I would only use unsigned when you care about things like being able to use all bit representations, then have made the all-1s number something like NaN, for ints.
- greenhouse_gas 8y agoThe real issue isn't that C doesn't have a standard int overflow, but that it's undefined. What they could have done is made it implementation defined, like sizeof(int), which depends on the implementation (hardware) but on the other hand isn't undefined behavior (so on x86/amd4 sizeof(int) will always be equal to 4).
- paulddraper 8y ago> on x86/amd4 sizeof(int) will always be equal to 4 Nothing is stopping your C compiler from making the guarantee sizeof(int)=4 on x86/amd64.
- wyldfire 8y agoI think you are in agreement with the comment you are replying to.
- paulddraper 8y agoThe comment suggested the standard make it implementation defined rather than undefined. There's not a meaningful difference here. Even today, an implementation may define unsigned overflow.
- wyldfire 8y agoOh, I see, I wonder if greenhouse_gas is suggesting a feature similar to sizeof() that can be used to portably adapt your program's design to the target's overflow capability.
- unwind 8y agoC language lawyer in training: sizeof is not a function. The parentheses are part of the operand and only needed for type names, to make them into cast expressions.
- Someone 8y ago
- ridiculous_fish 8y ago> Overflow in the positive direction shall wrap around This appears to be defining signed integer overflow semantics, which prevents the compiler from doing certain basic optimizations, for example, that (x*2)/2 == x. Is that part of this? Has anyone measured the perf cost on a real program?
- userbinator 8y agoIt prevents risky optimisations; this now requires the compiler to prove that such optimisations won't change the semantics of the code, e.g. in your case by essentially proving that the high 2 bits of x (only 1 in the unsigned case, due to sign-extension) will never be set. ...and it could be argued that if the compiler couldn't prove that was true, then it just helped you find a possible overflow bug in the code. If you actually wanted the compiler to unconditionally assume (x*2)/2==x and optimise accordingly, then you'd have to tell it such; e.g. MSVC has the __analysis_assume() feature.
- caf 8y agoHowever it also prevents "abort on overflow" implementations from being conforming, which look like a much better way of finding actual overflow bugs in the code.
- DoofusOfDeath 8y agoThat's a question of static vs. dynamic analysis for bug detection. Which one(s) is/are most useful depends on the user's needs.
- simias 8y agoStatic analysis was always possible, dynamic isn't if you want to remain standard-compliant and overflow is defined. That being said I think it's a rather weak justification for making overflow UB, after all if you want to trap on overflows wouldn't want to catch unsigned overflow as well?
- 8y ago
- microcolonel 8y agoThe equivalent for C/WG14: http://www.open-std.org/jtc1/sc22/wg14/www/docs/n2218.htm http://www.open-std.org/jtc1/sc22/wg14/www/docs/n2218.htm
- caf 8y agoThat document has this listed as a Change: Conversion from signed to unsigned is always well-defined: the result is the unique value of the destination type that is congruent to the source integer modulo 2ⁿ. ...but that's not a change - it's been the case in C all along.
- beyondCritics 8y agoGetting rid of this useless (crap #!§$§$§$) legacy stuff was overdue, so i am very happy to see it done. I personally think it is _the_ most important proposal for C++20, since it will remove a lot of pointless pressure from secure coding attempts and in turn make the world a little bit more secure.
- sanxiyn 8y agoI don't see how. Integer overflows still can be security issues even if they wrap.
- johannes1234321 8y agoThey can be security issues since the compiler is allowed to optimize stuff. The compiler can check, that some checks the user added "don't make sense" since those only would be hit if something undefined happens. An example is shown in https://www.tripwire.com/state-of-security/vulnerability-management/compiler-undermining-secure-coding/ https://www.tripwire.com/state-of-security/vulnerability-man... but there are many more.
- kazinator 8y agoNo, they can be security issues in that the program expected x + 1 to be a value bigger than x, but it is suddenly a big negative value. The fact that this behavior is now blessed by ISO C makes no difference to it being wrong, and causing some security issue in the program.
- beyondCritics 8y agoThere will always be unavoidable issues, since C/C++ is a system language, designed to survive under tight performance pressure. The point here is, to remove pointless obstacles.
- loup-vaillant 8y agoAlas, nope. Later revisions of this proposal still have undefined signed overflow. We still need -fwrap for the easy overflow checks.
- FrozenVoid 8y agoFYI you can prevent all of non-2 complement problems with -fwrapv which forces 2' complement wrapping math in gcc/clang/icc
- jgtrosh 8y agoQuick question: in the proposed rewording of intro.execution¶8, why is the following rewriting “((a + b) + 32765)” not reintegrated at the end of the untouched text? Have I misunderstood that with two's complement this would be legal?
- raverbashing 8y ago> Naïve overflow checks, which are often security-critical, often get eliminated by compilers. This leads to exploitable code when the intent was clearly not to and the code, while naïve, was correctly performing security checks for two’s complement integers. This is the most critical aspect. We have enough trouble already without the compiler actually fighting against security because this would fail in a machine from the 70s
- sanxiyn 8y agoThis got rejected in the next revision of this proposal. Naive overflow checks are still undefined.
- gpvos 8y agoOkay, then the proposal is already mostly useless.
- dzdt 8y agoIf a signed operation would naturally produce a value that is not within the range of the result type, the behavior is undefined. The author had hoped to make this well-defined as wrapping (the operations produce the same value bits as for the corresponding unsigned type), but WG21 had strong resistance against this. Who are the standards committee people having strong resistance against this, and what in the world is their argument?
- kazinator 8y agoUndefined doesn't mean incorrect; it's just the absence of a requirement. A compiler writer can add requirements locally (like "signed integer overflows have wrapping behavior") that are missing in the standard. The standard is not a suitable babysitting tool for GCC maintainers, which is what I suspect is the motivation here.
- yoklov 8y agoThis isn’t entirely untrue in theory, but in practice it is. Compilers optimize under the assumption that undefined behavior never occurs, and the standard is written with this assumption. Any conforming compiler is free to break code that relies on this. Typically, behavior that reasonably may vary from compiler/machine is considered implementation defined, and not undefined.
- lloda 8y agoThe link is an outdated version r0, this is r2 (don't know if it's the latest) http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2018/p0907r2.html http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2018/p090...
- jwilk 8y agoThe main change between [P0907r0] and the subsequent revision is to maintain undefined behavior when signed integer overflow occurs, instead of defining wrapping behavior.
- slededit 8y agoAnd the joy I originally had is once again lost.
- deleted 8y ago[deleted]
- badsectoracula 8y agoGah, what is the point then?
- sanxiyn 8y agoThe point is that signed integers are two's complement. After all, it is the title.
- barrkel 8y agoNaive overflow checks are often done by adding two positive numbers together and checking if the result is negative. If wrapping is undefined, this no longer works, and the overflow check may be eliminated.
- danra 8y agoYou can always get the most up-to-date public version using wg21.link/pxxxx. So for this proposal: https://wg21.link/p0907 https://wg21.link/p0907
- deleted 8y ago[deleted]
- GlitchMr 8y agoI like the idea of forbidding signed integer representations other than 2's complement, as it is de facto standard, pretty much nobody makes CPUs with non-standard integer representations, partly due to C programs assuming 2's complement integer representation. What I don't like about this proposal is defining signed integer overflow as 2's complement wrapping. Yes, yes, I know undefined behaviour is evil, and programs wouldn't become much slower. However, if a program has signed overflow, it's likely a bug anyway. Defining signed overflow as 2's complement wrapping would mean not allowing other behaviours, in particular, trapping. On architectures with optional overflow traps (most architectures not called x86 or ARM), trapping would be much more preferable to quiet bugs. Meanwhile, while it is undefined behaviour, the implementation would be still free to define it, for instance in GCC it can be done with `-fwrapv`.
- dEnigma 8y agoSeems like this was changed in more recent revisions, according to another comment: The main change between [P0907r0] and the subsequent revision is to maintain undefined behavior when signed integer overflow occurs, instead of defining wrapping behavior.
- loup-vaillant 8y ago> However, if a program has signed overflow, it's likely a bug anyway. There are programs that check for overflow after the fact. Is that a bug?
- sanxiyn 8y agoNo, but since most overflows are bugs, I think the right solution is to standardize something like GCC's __builtin_add_overflow for overflow checks. Rust does this.
- fanf2 8y agoAlso relevant is HAKMEM item 154 in which Bill Gosper concluded that the universe is two’s complement: http://catb.org/jargon/html/H/HAKMEM.html http://catb.org/jargon/html/H/HAKMEM.html
- kazinator 8y agoRequiring two's complement just means you can't have a sensible C language on some sign-magnitude machine. Even if nobody cares about such a machine, nothing is achieved other than perhaps simplifying a spec. A language spec can provide a more detailed two's complement model with certain behaviors being defined that only make sense on two's complement machines, without tossing other machines out the window. There could be a separate spec for a detailed two's complement model. That could be an independent document. (Analogy: IEEE floating-point.) Or it could be an optional section in ISO C. Two's complement has some nice properties, but isn't nice in other regards. Multi-precision integer libraries tend to use sign-magnitude, for good reasons. What I suspect is going on here is that someone is unhappy with what is going on in GCC development, and thinks ISO C is the suitable babysitting tool. (Perhaps a reasonable assumption, if those people won't listen to anything that doesn't come from ISO C.)
- mannykannot 8y agoThe worst case is that there would not be an ISO C for such machines. As they are very unusual, this does not strike me as a big deal, and definitely less of an issue than making it easier to avoid invoking undefined behavior. I take your point about the possible motives behind this proposal, which seem quite plausible.
- kazinator 8y agoBut gutting support for sign-magnitude machines has nothing to do with making certain two's complement behaviors defined. It's like saying we have to drop USB 1.0 support in an OS in order to fix missing features in the Bluetooth stack.
- mannykannot 8y agoI don't think that analogy works well, because if there was a dependency in standards that led to this outcome, would it not be better to break the dependency going forward, or to have avoided it in the first place? And not having an ISO C standard for sign-magnitude machines (which is not a necessary consequence of the proposed change, it is just the worst case, depending on how ISO chose to deal with the consequences for such machines) does not necessarily force an end to actual C support for them.
- polthrowaway 8y agohave they considered introducing new types for wrapping integers, checked integers and saturating integers. i understand why they might not want to make a change that could have a large effect on existing programs. but if you introduce new types then the new types will only effect new programs that choose to use them and this seems to be something that could be a library change than a language change.
- beyondCritics 8y agoThere seems to be an error in this proposal: "Change Conversion from signed to unsigned is always well-defined: the result is the unique value of the destination type that is congruent to the source integer modulo 2N." This is no change, since we have that already, e.g. see https://en.cppreference.com/w/cpp/language/implicit_conversion https://en.cppreference.com/w/cpp/language/implicit_conversi... and the conversion operation on the bit pattern is the identity for two's complement representation. The relevant section in the latest C++ standard is: 4.8 Integral conversions [conv.integral] 1 A prvalue of an integer type can be converted to a prvalue of another integer type. ... 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 ] Therefore the inverse conversion exists and is the identity as well, this is what should be sanctioned.