11 ms·

Two's complement integers with only sign bit set should be a trap representation

65 points by luu 3y ago

kevin_thibedeau 3y ago
Computers are implemented in hardware, not maths proofs. The Java generation is infatuated with magic numerics without realizing their performance cost.
- nine_k 3y ago
  Floating-point numbers are also directly supported by hardware, but they carved a few values for NaN, negative and positive infinity, and negative and positive zero. I don't see why integers should not have something similar, especially large enough integers, like i64 or even i32. Historically they don't though.
  - GrumpySloth 3y ago
    Floating point numbers also don’t obey normal algebra laws and are notoriously tricky to get right. Two’s complement on the other hand form an honest-to-god commutative ring, their implementation is dead simple and it’s very rare that they lead to bugs in and out of themselves. They’re one of the most beautiful solutions in computer science IMO. I’d give up floating point much more readily than two's complement.
- lxgr 3y ago
  What’s the “Java generation”, and why is premature optimization strictly preferred over sacrificing performance over correctness? x86 offers hardware traps for integer division by zero while PowerPC returns zero – does that make x86 more wasteful/a “Java generation CPU”? What about CPUs that support native wrap trapping?
  - AdamH12113 3y ago
    I think the GP's point is that this would need hardware support. Without that, it's not something you could implement efficiently as a programming language feature -- you'd have to "trap" by checking the result of every arithmetic operation in software.
    - lxgr 3y ago
      Python does just that for integers (since it automatically casts up to bigints instead of overflowing), as does Swift, and that's arguably fairly low-level/"compiled"! It doesn't strike me as an absurd idea. Compilers could optimize for common cases where overflows are guaranteed to not happen, or perform the "isn't b100..000" check at the entrance to an inner loop and defer to the hardware's native overflow detection capabilities (if any).
      - trealira 3y ago
        Lisp has converted fixnums (hardware integers) to bignums on overflow since the 1970s, too, so it's not just the "Java generation." Their words: > Computers are implemented in hardware, not maths proofs. The _ generation is infatuated with _ without realizing their performance cost. This sounds just like the assembly programmers arguing against high level languages, who were against the overhead of unlimited named variables and recursive function activation records. We should optimize for writing a lot of correct but slightly inefficient software. By keeping high-level language compilers (rather than assembly language programmers) in mind for the design of newer ISAs, we already have, to some extent. That said, I still don't know about making the lowest signed number a trap representation in hardware. We already usually have a flag to detect signed overflow; why not just check that?
        lxgr 3y ago
        > That said, I still don't know about making the lowest signed number a trap representation in hardware. We already usually have a flag to detect signed overflow; why not just check that? TFA mentions efficient representation of optional/nilable integers in parameters or return values as another benefit, which I do have some sympathy for (supplying MIN_INT or MAX_INT as an effective "nil" value has always felt wrong to me). I'm not sure if a hardware trap is the right mechanism to handle that, though.
- usrusr 3y ago
  I'd say the only "generational" part is that in this example the question has made it to the web. Who wouldn't wonder, when first leaning about two's complement, if unsigned plus sign (one's complement) might be preferable? I'd rather question the mind of people who never went through that phase. And the people who, in the early days, opted for one's complement for the hardware they designed certainly did not do so because of being too far from the metal. Both representations coexisted for a while, sometimes within the same system.
  - sham1 3y ago
    For slight pedantry, "unsigned plus sign" is the sign-and-magnitude representation, while one's complement negation is taking the bitwise NOT of the number in question.
- saagarjha 3y ago
  Why do you think the author of this is unaware of the performance cost?
lifthrasiir 3y ago
I would welcome something like sNaN but actually fully enforced and widely implemented in hardwares. Otherwise it would be just a pipe dream.
kazinator 3y ago
> should be a trap representation In a new, green field programming language design: maybe. You will have FFI interop issues: what if some foreign gives you such a value, which is correct in its domain. It will have to be specially handled and widened/promoted to a type that can hold it. It looks like friction, though. In an existing language, like C? Making currently correct programs blow up with a trap exception is a nonstarter. I think there is no hardware support for treating 0x80... as a trap, so if you actually want it to trap, rather than leaving it at undefined behavior, your compiler has to emit check code, at least in code paths where it is not obvious whether the value is or isn't a trap. Also, it would be strangely inconsistent for the 0x80... to predictably trap wherever it occurs, but arithmetic overflow to have undefined consequences. The two want to be tied together.
- owlbite 3y ago
  Also bitfields / any application using the hi bit as a flag for something or other is going to break now.
- kelnos 3y ago
  > You will have FFI interop issues: what if some foreign gives you such a value, which is correct in its domain. It will have to be specially handled and widened/promoted to a type that can hold it. That's more or less what you have to do in Java if your FFI is passing you an unsigned type. You need to use a 64-bit signed long in Java to hold a uint32_t, and a BigInteger to hold a uint64_t. I mean, you can certainly store that unsigned 32-bit int from the FFI call in a 32-bit signed Java int, but then you have to use special methods on the Integer class to do unsigned comparisons and arithmetic. Agreed, this is a lot of friction, but there's long-standing precedent, at least.
- dkjaudyeqooe 3y ago
  This is a simplistic view. I implement nil/null values everywhere including integers and at the external border there is a test for that special value. It's not like you're using this sort of thing for just another number so it's natural that there is an adaption.
- UncleMeat 3y ago
torstenvl 3y ago
Wait so we're going to give up -fwrapv (a UB mitigation) for the explicit purpose of introducing more undefined behavior? I don't see any way this change wouldn't lead to an enormous number of bugs, all for the (dubious) goal of having the range of signed integers be symmetrical.
- atq2119 3y ago
  I think the idea is that overflowing would be a guaranteed trap of some kind, i.e. defined behavior.
- eru 3y ago
  You don't have to introduce more undefined behaviour. A trap could be very defined behaviour.
  - torstenvl 3y ago
    No. What? No. A trap is by definition undefined behavior. "Certain object representations need not represent a value of the object type. If the stored value of an object has such a representation and is read by an lvalue expression that does not have character type, the behavior is undeﬁned. If such a representation is produced by a side effect that modiﬁes all or any part of the object by an lvalue expression that does not have character type, the behavior is undeﬁned."
    - akoboldfrying 3y ago
      I think the idea would be to redefine "the object type" to make the trap value valid -- and to define the result of all operators on the trap value in some sensible way (similar to non-signalling NaNs in IEEE-754 floating point), so that, e.g., adding the trap value and any number produces the trap value again.
      - torstenvl 3y ago
        It is not possible for a trap representation to be made valid. A trap representation is one where getting it or setting it, other than as a raw byte, is undefined behavior. Section 6.2.6.1, paragraph 5, of C99, C11, C17, and—with a terminology change—the final draft of C23 are crystal clear on this.
femto 3y ago
DSPs already do something like this, offering the option of saturating arithmetic operations, in addition to the normal modulo arithmetic. It's the operation that's special, not the representation in memory. The normal way to do it is to use the "ETSI Basic Operator" library, which provides saturating arithmetic operations, among other things [1]. If the hardware supports saturated arithmetic the compiler maps the operations to the relevant instructions, otherwise it provides a software implementation. Example: Modulo arithmetic: int16_t a,b,c; a = b + c; Saturating 16-bit arithmetic using ETSI: int16_t a,b,c; a = add(b, c); [1] https://www.itu.int/rec/T-REC-G.191/en https://www.itu.int/rec/T-REC-G.191/en
- Stenzel 3y ago
  Processors with saturating capabilities usually clip at 0x7FFFFFF and 0x80000000, so the clipping thing has no relation to the original topic. But in fixpoint DSP, 0x8000 (add trailing zeros if you like) is often the only possibility to achieve a multiplicative identity by using a = - b * 0x8000, with the negation part of the assembly instruction.
nynx 3y ago
Please no. A process dying automatically and immediately dying because of an arithmetic overflow would be terrible.
- Dylan16807 3y ago
  You can have a handler. But are you sure exiting is more terrible than blindly forging ahead with a known-wrong number?
  - nynx 3y ago
    Who said overflow was wrong? The sort of code I work on has to continue running, no matter what. Continuing on is always better than crashing, at least in my context. It’s also basically impossible to establish invariants about a system for code that is run in signal handlers
    - lxgr 3y ago
      And I’ll take a crash over a silent wraparound any day. Out of curiosity, what domain is that? I can’t think of many use case where silent wrapping wouldn’t likely cause problems down the road.
      - nynx 3y ago
        I write software for spacecraft. I’d much rather take my chances that the overflowed value is meant for humans or for some tertiary system than to end the mission regardless.
        bvrmn 3y ago
        Oh shi, not very reassuring knowledge spacecraft SW engineers allow signed overflow in their code.
        Am4TIfIsER0ppos 3y ago
dreamcompiler 3y ago
One of the things I love about Lisp is that i+1 is always greater than i. You can work hard to make that not be true, but that's the default and IMHO it's the proper default.
- eru 3y ago
  Well, that's the case for signed integers in C as well. (But only on a technicality: because every program where that breaks is not technically C, and the compiler is allowed to assume this doesn't happen.) I suspect the Lisps you talk about use arbitrary sized integers by default? Python also has that default. It's a good default. If you want to optimize for size and want an integer of limited size, like a 64 bits or so, you should explicitly specify.
  - MathMonkeyMan 3y ago
    Yep, the [numerical tower][1]. Python's int is a bignum, but in Scheme you even have rationals built in. There's a notion of which numeric values are "exact" and which ones are "inexact" (i.e. floating point). [1]: https://en.wikipedia.org/wiki/Numerical_tower https://en.wikipedia.org/wiki/Numerical_tower
    - eru 3y ago
      I remember the numerical tower from Scheme. That was an interesting concept. (Though mathematically, you might want something with a more complicated structure than a tower. Eg p-adic numbers would sit below integers, next to rational numbers, but not below them.) Python has rational numbers in the standard library. They are easy to use there, too.
      - waqf 3y ago
        Every rational number is a p-adic number (though not necessarily a p-adic integer, of course). So doesn't that mean p-adic numbers would be below rationals?
adgjlsfhk1 3y ago
the version of this I've really wanted is hardware support for integers mod 2^64-1 with 0x1000000000000000 as a nan value. the addition and subtraction and division would be trivial. multiplication would be a tiny bit more complicated, but should be relatively doable. there are 3 main advantages with this system 1. ability to properly represent zero division or overflow without flags/exceptions 2. abs(x) is always greater than 0 3. a mix of these and regular Ints could be used with the Chinese remainder theorem to provide faster (almost) 128 bit math.
- adgjlsfhk1 3y ago
  I would also be in favor of doing this for floating point (get rid of +-Inf, and -0.0 and make the only NaN value be the bitwise negation of 0.0).
eru 3y ago
From the linked discussion: > @jrose @fclc People who want NaN in their integers are welcome to do that in the privacy of their own bedrooms with new types they invent for this purpose. That reminds me of OCaml's 63 bit integers. In the privacy of OCaml's own bedroom, they use one bit of their integers as a flag to distinguish pointers from integers. See https://blog.janestreet.com/what-is-gained-and-lost-with-63-bit-integers/ https://blog.janestreet.com/what-is-gained-and-lost-with-63-... The results are quite.. interesting. However, it does go to show that having slightly weird private integer types is actually totally workable, so the quote from the discussion might be meant as trolling, but it's less crazy than it sounds like.
- rob74 3y ago
  The difference is that (a) that bit in OCaml has a purpose, while disregarding 0x80..00 hasn't; and (b) I assume that it was in OCaml from the beginning, so it wouldn't break existing software in probably very interesting ways (hence the suggestion that this should be done only "in the privacy of their own bedrooms with new types", i.e. not for already-used types)...
  - JKCalhoun 3y ago
    Yes, correct me if I'm wrong, but I thought the point was that 0x8000 is like negative zero and so of no utility, redundant. So let's make it useful.
    - mbel 3y ago
      It's not. 0x8000 is the smallest (-32,768) integer that can be represented with 16-bits and two's complement.
      - taeric 3y ago
        Yeah, I think it is funny that in a standard binary, it would replace negative zero and makes some sense. In two's complement, it replaces the minimum value. Fair that sentinel value is sentinel value, I suppose. But it is not like it is not a known and unique number in that encoding.
gregfjohnson 3y ago
Here is my favorite example of errors due to overflow: std::vector<int> vec; // test for sorted.. bool sorted = true; for (size_t i = 0; i < vec.size() - 1ULL; ++i) if (vec[i] > vec[i+1]) { sorted = false; break; } I believe the google c++ style guide rues the selection of unsigned integers as the return type of size() in the standard library for reasons like the above. Personally, my preferred behavior would be to have a compiler flag that could be used to enable a trap if unsigned arithmetic resulted in wrap-around, as in the above case when the vector is of length zero.
- planede 3y ago
  > Personally, my preferred behavior would be to have a compiler flag that could be used to enable a trap if unsigned arithmetic resulted in wrap-around, as in the above case when the vector is of length zero. That probably has the potential of having too many false positives. It's also very non-confroming, so I see why compiler vendors would be reluctant to add such a flag.
- jcelerier 3y ago
  > compiler flag that could be used to enable a trap if unsigned arithmetic resulted in wrap-around, as in the above case when the vector is of length zero. I mean.. this is exactly what -fsanitize=integer does in clang. I never saw a signed overflow UB, but how many "perfectly defined" yet horrendously wrong cases like this one this sanitizer has helped me find...
  - gregfjohnson 3y ago
    Thanks so much - I was unaware of this clang flag. I just confirmed, it does exactly what I was hoping for! I suggested that this be an optional flag, not the default behavior. I could see using it for unit-test/static-analysis builds where performance is not the main concern. (I have not looked at the generated assembly or done a performance comparison, but it might be that the -fsanitize=integer flag would slow the generated code down.)
    - 3y ago
adrian_b 3y ago
In the past I have also been tempted by this idea that perhaps it would be better to redefine the current INT_MIN to be a NaN. Nevertheless, after thinking more about it, my conclusion was that this is not useful. The strongest argument in favor of it is that then an optional integer needs only the same size as an integer. Against this argument is the fact that in decades of programming I have never encountered the need for an optional integer type which needs for its base integer type all possible values. What I have encountered very frequently were optional integer types whose base integer type should have been defined as an integer interval a.k.a. integer range, like it is possible in languages like Ada or Pascal. For such optional integers with the valid values restricted to an interval, the optional type does not require extra storage over the base type, because the NaN can be represented by any value outside the permissible interval. The second argument for redefining INT_MIN to be a NaN is that this eliminates the possibility of overflows in several integer functions, like absolute value and negation. This argument is weak, because overflows can still happen in the more frequent arithmetic operations, so most non-trivial programs must still provide means to handle such exceptional cases. Moreover, the exceptions are avoided in absolute value and the like, by still having a (possibly implicit, i.e. inserted by the compiler) check that an integer value is not a NaN, somewhere before the code that uses negation, divide by -1, etc., perhaps in the invoking function, not in the invoked function to which integer arguments are passed, so this in the best case replaces multiple checks interspersed with the operations with a single check in the beginning, at the origin of the integer data. On the other hand, implicit checks that an integer is not a NaN would have to be added after additions and the like. The same is available now, in much of the code where integer overflows are possible one can check the range of the input integer data somewhere in the beginning, verifying that there are no values that can result in an overflow, avoiding further checks at each operation. The redefining of INT_MIN to be a NaN could help by relying on implicit checks added by a compiler in a few cases, but most expressions contain additions, subtractions and multiplications, so the program must still rely either on the compiler adding implicit overflow trap checks after each operation, for which adding the integer NaN does not give any improvements, or in the programmer writing explicit range checks that depend on the expressions that are computed, and for the majority of the expressions the explicit checks would still be needed.
tialaramex 3y ago
This is what nook:Balanced{I8,I16,I32,I64} are for. https://crates.io/crates/nook https://crates.io/crates/nook Of course today in Rust we're not allowed to bless such types for ourselves, this is reserved to the standard library (core::num::NonZeroU32 is a 4-byte unsigned integer which can't be zero for example) because it's relying on a nasty permanently unstable compiler-only feature to say "Hey, not all possible representations the right size for this type are valid". Rust has one very obvious set of types with such a niche, the references &T, but it also has not only the particular custom integers NonZero{U8,U16,U32,U64,I8,I16,I32,I64} and the Non-null pointers, but OS specific types (for Unix file descriptors, and Windows handles respectively) and of course char, it is 4 bytes but Unicode is explicitly limited to far fewer values, so that's a niche too. But today making more is not allowed in stable Rust, so while my nook crate is an interesting curiosity (and some day I'll implement integer math traits etc.) it cannot be stabilised and I was persuaded that the path forward is a whole lot of work to deliver the Pattern Types feature which can do this stably.
- kibwen 3y ago
  > permanently unstable compiler-only feature Arbitrary niches aren't intended to be permanently unstable (at least not in the sense of explicit implementation details like lang items and intrinsics), people have expressed a desire to stabilize them for years (as discussed during the original nonzero int types RFC). If something has changed in that regard, I'd appreciate a link to a discussion.
  - tialaramex 3y ago
    The niche concept isn't permanently unstable, but the present mechanism is. Today the only way to make such a type is to use the magic attributes #[rustc_nonnull_optimization_guaranteed] #[rustc_layout_scalar_valid_range_start] and #[rustc_layout_scalar_valid_range_end] As their names hint, these are permanently unstable compiler-only type hints. I asked that some means be found to stabilize some equivalent hint (presumably with a name that doesn't look like a compiler-only feature) in one of the long series of tickets spawned after 3334 and I was persuaded that this is a terrible idea and won't happen. Instead the proposed path forward is (at least was then) Pattern Types. Build at least an MVP of the full blown Pattern Types feature instead of a custom attribute.
hoseja 3y ago
None of signed integer representations are very good, each has severe drawbacks.
flohofwoe 3y ago
At that point, why not introduce special i63 and u63 types and use the hidden bit 63 as 'soft carry flag' to detect over/undeflow. 63 bits of integer range ought to be enough for anyone ;) (as soon as bit 63 is set, the number would be in 'overflow state', but at the same time the lower 63 bits would preserve the wrap-around value in case that's useful). On the other hand, compilers are already free to check the CPU carry flag bit and trap on it. Those flag bits are just not exposed to programming languages (which IMHO is a serious 'dissonance' between assembly and high level languages), also CPU flags can't be carried around with their associated result value and go 'viral' like NaNs (but whether that's even useful instead of trapping immediately is another question).
- jusuhi 3y ago
  Because i63 won't help with 32 bit variables.
  - flohofwoe 3y ago
    ...which is a bit of a weak reason when there are hardly any 32-bit CPUs around anymore though. Picking a narrower integer type makes sense in specific situations like tightly packed structs, but in that case it usually doesn't matter whether the integer range is 2^31 or 2^32, if you really need the extra bit of range it's usually ok to go to the next wider integer type.
    - jusuhi 3y ago
      Feel free to generalize my argument to i31 and i15. Also, look around you and realize that non-64-bit microprocessors outnumber 64-bit machines by orders of magnitude. There is more to the world than your laptop and smartphone. (Just within 1m of myself at this very moment I see 4 devices with a 32 bit microprocessor in them, and I'm sitting in a coffee shop reading a book. Well, and browsing HN now and then.)
      - flohofwoe 3y ago
        There's actually a better solution if you allow the compiler some wiggle room: Zig and C23 (and probably a couple other languages) support arbitrary width integers, so integer types like u15, i3, i1 or even u512 etc... are something entirely 'normal', and even useful in day-to-day coding when mixing signed and unsigned integer math (for instance Zig disallows to assign an unsigned integer to a signed integer of the same width, but it's perfectly fine to assign a 7-bit unsigned integer to an 8-bit signed integer). Down on the CPU such operations happen on the register width, and if the integer width exceeds the register width, are unrolled into a chain of op-with-carry instructions (same way we did 16- or 32-bit math back on 8-bit processors).
simiones 3y ago
Even if the current INT_MIN were redefined to be a NaN or a trap, that would do almost nothing to prevent signed integer overflow bugs. Sure, INT_MAX + 1 would be an error, but INT_MAX+2, INT_MAX+100 and so on would still be equal to INT_MIN + 1, INT_MIN + 99 etc. Besides, -fwrapv was basically the default in most C compilers (and probably C++ as well) before the last 10 years or so. Many large systems thus use it today as well (e.g. the Linux kernel, I believe).
- trealira 3y ago
  > Besides, -fwrapv was basically the default in most C compilers (and probably C++ as well) before the last 10 years or so. It seems like people were complaining as early as 2007. Richard Biener (who's linked in the thread link below) said that GCC 2.95.3, which came in 2001, optimized away signed overflow checks as well. https://gcc.gnu.org/bugzilla/show_bug.cgi?id=30475 https://gcc.gnu.org/bugzilla/show_bug.cgi?id=30475 --- > signed type overflow is undefined by the C standard, use unsigned int for the > addition or use -fwrapv You have GOT to be kidding? All kinds of security issues are caused by integer wraps, and you are just telling me that with gcc 4.1 and up I cannot test for them for signed data types any more?! You are missing the point here. There HAS to be a way to get around this. Existing software uses signed int and I can't just change it to unsigned int, but I still must be able to check for a wrap! There does not appear to be a work around I could do in the source code either! Do you expect me to cast it to unsigned, shift right by one, and then add or what?! PLEASE REVERT THIS CHANGE. This will create MAJOR SECURITY ISSUES in ALL MANNER OF CODE. I don't care if your language lawyers tell you gcc is right. THIS WILL CAUSE PEOPLE TO GET HACKED. I found this because one check to prevent people from getting hacked failed. THIS IS NOT A JOKE. FIX THIS! NOW!
  - simiones 3y ago
    Thanks for looking into the history! Interesting to see that this wrong-headed behavior has now been around in GCC for longer than the status quo before. Other compilers are different though - MSVC only seems to have started optimizing around this in ~2016 or so, icc seems to have done something around this in 2020, and I'm sure many embedded compilers ignore it even today. I couldn't find anything definitive on clang, but given its history I assume it probably always enforced this mistake. I'd also note that several major C programs only work when signed integer overflow is defined: I mentioned Linux previously, but Python is another one. And Chrome and Firefox are considering enabling -fwrapv and equivalents.
silvestrov 3y ago
Rather than a trap representation I'd like a real trap, i.e. exception at runtime that can be caugth. Propagated NULL is useful in SQL but likely much less for integers as they are used as indexes. It is difficult to say when the "NaN" should result in a trap when doing pointer arithmetic using such numbers as the CPU does not have seperate pointer/integer data types. There are so many security problems from integer overflow. Also some easy way of checking an integer is in the range [0...n[ as a single instruction that traps if it is not.
drhagen 3y ago
R does this [1]. It is the sentinel that it uses internally to represent a missing value (i.e. NA) in integer arrays. Integer operations overflow to this value. [1] https://stackoverflow.com/a/56507840/1485877 https://stackoverflow.com/a/56507840/1485877
z29LiTp5qUC30n 3y ago
So they want symmetric complement of the ancient Knight Processor where there was NaN encoded so that divide by zero wasn't an exception but just a return NaN.
snickerbockers 3y ago
This person's mind is going to be blown when he learns about bitmasks.
planede 3y ago
A trap representation is not a NaN-like sentinel value. The post also didn't discuss the updated semantics of integer operations, but I assume it just simply shrinks the range of representable values by removing -2^(N-1), and operations with a resulting value that lie outside are still undefined. Having a NaN-like sentinel with is another option, with overflowing integer operations defaulting to that value instead, but that's not what is proposed here. The post does mention optional<int>, which could have the NaN-like sentinel (empty optional) by reusing the bit-pattern of the trap representation of the underlying int.
scotty79 3y ago
All is fun and games until your negative number is suprisingly off by one because somebody, somewhere didn't convert between two complement and "symmetrical" ints correctly
fargle 3y ago
this strikes me as a chesterton's fence situation - "what kind of weird nonsense is this 2's complement where it's asymmetric (yuck) and you can't negate -0x8000" i seriously doubt the folks who think this is a good idea know enough about the math and computer architecture to understand why in fact it's a terrible idea. - programming languages are abstractions. but (old joel) leaky ones sometimes. we don't like this, but you have to live with it. - in this case, the choice might be between reality-leaks such as "integers have limits", "the limits are asymmetric, leading to this negation pseudo-paradox" and a much worse leak such as "why does this spiffy safe integer type run 100,000 times slower than the weird C int" - actually math itself is a series of ever complicated abstractions. first counting numbers. then ZERO. then NEGATIVE numbers. ACK! now wait until you get to Fields and Rings and Galois Fields, which are very close to the concept of 2's complement integers. i believe that if ignoring the botched C standard that makes signed integer wraparound UB, "normal" 2's complement integers (and unsigned) form a finite ring. - so what? well even these fancy, and frankly, impenetrable math abstractions are just abstractions. they leak too and aren't "perfect" if you take into account the real universe which doesn't always match the perfect math. doesn't mean it isn't very useful. - these concepts can be used to reason about the behavior physical things, like the behavior of an array of flip-flops representing a 64 bit number and especially how you can create circuits and simplify them to do things that implement addition, multiplication, etc. - the problem with a sorta-1's-complement-without-two-zeros idea is it has none of these connections to grounded theoretical basis. so how do you simplify an adder? can you perform algebraic simplifications to it? what is the model for this thing? - symmetry is in the eye of the beholder. draw a 4-bit signed 2's complement drawing using "clock diagram". it works. now do it with 1's complement or this suggestion which is even worse with an odd, sometimes prime, number of nodes. - implementation: 2's complement is a very clever hardware technique that lets you interpret N bits as N digits of a binary number. each digit has weight 2^n: 1, 2, 4, 8, etc. except the last digit which has weight -2^n. this simple trick lets the signed and unsigned integers use the same addition, subtraction, and with minor processing, multiplication and division logic unchanged. it's very unlikely that you can implement the suggested scheme at even 1/10th the performance or cost. - and, yes, i think C really got it wrong calling "overflow" or wraparound UB. if it was defined to wrap, at least it would be theoretically analyzable. you'd still have overflow flaws, but that's provably impossible to avoid with finite sized integers of any design.

65 points by luu 3y ago

Computers are implemented in hardware, not maths proofs. The Java generation is infatuated with magic numerics without realizing their performance cost.

nine_k 3y ago
Floating-point numbers are also directly supported by hardware, but they carved a few values for NaN, negative and positive infinity, and negative and positive zero. I don't see why integers should not have something similar, especially large enough integers, like i64 or even i32. Historically they don't though.
- GrumpySloth 3y ago
  Floating point numbers also don’t obey normal algebra laws and are notoriously tricky to get right. Two’s complement on the other hand form an honest-to-god commutative ring, their implementation is dead simple and it’s very rare that they lead to bugs in and out of themselves. They’re one of the most beautiful solutions in computer science IMO. I’d give up floating point much more readily than two's complement.
lxgr 3y ago
What’s the “Java generation”, and why is premature optimization strictly preferred over sacrificing performance over correctness? x86 offers hardware traps for integer division by zero while PowerPC returns zero – does that make x86 more wasteful/a “Java generation CPU”? What about CPUs that support native wrap trapping?
- AdamH12113 3y ago
  I think the GP's point is that this would need hardware support. Without that, it's not something you could implement efficiently as a programming language feature -- you'd have to "trap" by checking the result of every arithmetic operation in software.
  - lxgr 3y ago
    Python does just that for integers (since it automatically casts up to bigints instead of overflowing), as does Swift, and that's arguably fairly low-level/"compiled"! It doesn't strike me as an absurd idea. Compilers could optimize for common cases where overflows are guaranteed to not happen, or perform the "isn't b100..000" check at the entrance to an inner loop and defer to the hardware's native overflow detection capabilities (if any).
    - trealira 3y ago
      Lisp has converted fixnums (hardware integers) to bignums on overflow since the 1970s, too, so it's not just the "Java generation." Their words: > Computers are implemented in hardware, not maths proofs. The _ generation is infatuated with _ without realizing their performance cost. This sounds just like the assembly programmers arguing against high level languages, who were against the overhead of unlimited named variables and recursive function activation records. We should optimize for writing a lot of correct but slightly inefficient software. By keeping high-level language compilers (rather than assembly language programmers) in mind for the design of newer ISAs, we already have, to some extent. That said, I still don't know about making the lowest signed number a trap representation in hardware. We already usually have a flag to detect signed overflow; why not just check that?
      - lxgr 3y ago
        > That said, I still don't know about making the lowest signed number a trap representation in hardware. We already usually have a flag to detect signed overflow; why not just check that? TFA mentions efficient representation of optional/nilable integers in parameters or return values as another benefit, which I do have some sympathy for (supplying MIN_INT or MAX_INT as an effective "nil" value has always felt wrong to me). I'm not sure if a hardware trap is the right mechanism to handle that, though.
usrusr 3y ago
I'd say the only "generational" part is that in this example the question has made it to the web. Who wouldn't wonder, when first leaning about two's complement, if unsigned plus sign (one's complement) might be preferable? I'd rather question the mind of people who never went through that phase. And the people who, in the early days, opted for one's complement for the hardware they designed certainly did not do so because of being too far from the metal. Both representations coexisted for a while, sometimes within the same system.
- sham1 3y ago
  For slight pedantry, "unsigned plus sign" is the sign-and-magnitude representation, while one's complement negation is taking the bitwise NOT of the number in question.
saagarjha 3y ago
Why do you think the author of this is unaware of the performance cost?

lifthrasiir 3y ago

I would welcome something like sNaN but actually fully enforced and widely implemented in hardwares. Otherwise it would be just a pipe dream.

kazinator 3y ago

> should be a trap representation In a new, green field programming language design: maybe. You will have FFI interop issues: what if some foreign gives you such a value, which is correct in its domain. It will have to be specially handled and widened/promoted to a type that can hold it. It looks like friction, though. In an existing language, like C? Making currently correct programs blow up with a trap exception is a nonstarter. I think there is no hardware support for treating 0x80... as a trap, so if you actually want it to trap, rather than leaving it at undefined behavior, your compiler has to emit check code, at least in code paths where it is not obvious whether the value is or isn't a trap. Also, it would be strangely inconsistent for the 0x80... to predictably trap wherever it occurs, but arithmetic overflow to have undefined consequences. The two want to be tied together.

owlbite 3y ago
Also bitfields / any application using the hi bit as a flag for something or other is going to break now.
kelnos 3y ago
> You will have FFI interop issues: what if some foreign gives you such a value, which is correct in its domain. It will have to be specially handled and widened/promoted to a type that can hold it. That's more or less what you have to do in Java if your FFI is passing you an unsigned type. You need to use a 64-bit signed long in Java to hold a uint32_t, and a BigInteger to hold a uint64_t. I mean, you can certainly store that unsigned 32-bit int from the FFI call in a 32-bit signed Java int, but then you have to use special methods on the Integer class to do unsigned comparisons and arithmetic. Agreed, this is a lot of friction, but there's long-standing precedent, at least.
dkjaudyeqooe 3y ago
This is a simplistic view. I implement nil/null values everywhere including integers and at the external border there is a test for that special value. It's not like you're using this sort of thing for just another number so it's natural that there is an adaption.
UncleMeat 3y ago

torstenvl 3y ago

Wait so we're going to give up -fwrapv (a UB mitigation) for the explicit purpose of introducing more undefined behavior? I don't see any way this change wouldn't lead to an enormous number of bugs, all for the (dubious) goal of having the range of signed integers be symmetrical.

atq2119 3y ago
I think the idea is that overflowing would be a guaranteed trap of some kind, i.e. defined behavior.
eru 3y ago
You don't have to introduce more undefined behaviour. A trap could be very defined behaviour.
- torstenvl 3y ago
  No. What? No. A trap is by definition undefined behavior. "Certain object representations need not represent a value of the object type. If the stored value of an object has such a representation and is read by an lvalue expression that does not have character type, the behavior is undeﬁned. If such a representation is produced by a side effect that modiﬁes all or any part of the object by an lvalue expression that does not have character type, the behavior is undeﬁned."
  - akoboldfrying 3y ago
    I think the idea would be to redefine "the object type" to make the trap value valid -- and to define the result of all operators on the trap value in some sensible way (similar to non-signalling NaNs in IEEE-754 floating point), so that, e.g., adding the trap value and any number produces the trap value again.
    - torstenvl 3y ago
      It is not possible for a trap representation to be made valid. A trap representation is one where getting it or setting it, other than as a raw byte, is undefined behavior. Section 6.2.6.1, paragraph 5, of C99, C11, C17, and—with a terminology change—the final draft of C23 are crystal clear on this.

femto 3y ago

DSPs already do something like this, offering the option of saturating arithmetic operations, in addition to the normal modulo arithmetic. It's the operation that's special, not the representation in memory. The normal way to do it is to use the "ETSI Basic Operator" library, which provides saturating arithmetic operations, among other things [1]. If the hardware supports saturated arithmetic the compiler maps the operations to the relevant instructions, otherwise it provides a software implementation. Example: Modulo arithmetic: int16_t a,b,c; a = b + c; Saturating 16-bit arithmetic using ETSI: int16_t a,b,c; a = add(b, c); [1] https://www.itu.int/rec/T-REC-G.191/en https://www.itu.int/rec/T-REC-G.191/en

Stenzel 3y ago
Processors with saturating capabilities usually clip at 0x7FFFFFF and 0x80000000, so the clipping thing has no relation to the original topic. But in fixpoint DSP, 0x8000 (add trailing zeros if you like) is often the only possibility to achieve a multiplicative identity by using a = - b * 0x8000, with the negation part of the assembly instruction.

nynx 3y ago

Please no. A process dying automatically and immediately dying because of an arithmetic overflow would be terrible.

Dylan16807 3y ago
You can have a handler. But are you sure exiting is more terrible than blindly forging ahead with a known-wrong number?
- nynx 3y ago
  Who said overflow was wrong? The sort of code I work on has to continue running, no matter what. Continuing on is always better than crashing, at least in my context. It’s also basically impossible to establish invariants about a system for code that is run in signal handlers
  - lxgr 3y ago
    And I’ll take a crash over a silent wraparound any day. Out of curiosity, what domain is that? I can’t think of many use case where silent wrapping wouldn’t likely cause problems down the road.
    - nynx 3y ago
      I write software for spacecraft. I’d much rather take my chances that the overflowed value is meant for humans or for some tertiary system than to end the mission regardless.
      - bvrmn 3y ago
        Oh shi, not very reassuring knowledge spacecraft SW engineers allow signed overflow in their code.
        Am4TIfIsER0ppos 3y ago

dreamcompiler 3y ago

One of the things I love about Lisp is that i+1 is always greater than i. You can work hard to make that not be true, but that's the default and IMHO it's the proper default.

eru 3y ago
Well, that's the case for signed integers in C as well. (But only on a technicality: because every program where that breaks is not technically C, and the compiler is allowed to assume this doesn't happen.) I suspect the Lisps you talk about use arbitrary sized integers by default? Python also has that default. It's a good default. If you want to optimize for size and want an integer of limited size, like a 64 bits or so, you should explicitly specify.
- MathMonkeyMan 3y ago
  Yep, the [numerical tower][1]. Python's int is a bignum, but in Scheme you even have rationals built in. There's a notion of which numeric values are "exact" and which ones are "inexact" (i.e. floating point). [1]: https://en.wikipedia.org/wiki/Numerical_tower https://en.wikipedia.org/wiki/Numerical_tower
  - eru 3y ago
    I remember the numerical tower from Scheme. That was an interesting concept. (Though mathematically, you might want something with a more complicated structure than a tower. Eg p-adic numbers would sit below integers, next to rational numbers, but not below them.) Python has rational numbers in the standard library. They are easy to use there, too.
    - waqf 3y ago
      Every rational number is a p-adic number (though not necessarily a p-adic integer, of course). So doesn't that mean p-adic numbers would be below rationals?

adgjlsfhk1 3y ago

the version of this I've really wanted is hardware support for integers mod 2^64-1 with 0x1000000000000000 as a nan value. the addition and subtraction and division would be trivial. multiplication would be a tiny bit more complicated, but should be relatively doable. there are 3 main advantages with this system 1. ability to properly represent zero division or overflow without flags/exceptions 2. abs(x) is always greater than 0 3. a mix of these and regular Ints could be used with the Chinese remainder theorem to provide faster (almost) 128 bit math.

adgjlsfhk1 3y ago
I would also be in favor of doing this for floating point (get rid of +-Inf, and -0.0 and make the only NaN value be the bitwise negation of 0.0).

eru 3y ago

From the linked discussion: > @jrose @fclc People who want NaN in their integers are welcome to do that in the privacy of their own bedrooms with new types they invent for this purpose. That reminds me of OCaml's 63 bit integers. In the privacy of OCaml's own bedroom, they use one bit of their integers as a flag to distinguish pointers from integers. See https://blog.janestreet.com/what-is-gained-and-lost-with-63-bit-integers/ https://blog.janestreet.com/what-is-gained-and-lost-with-63-... The results are quite.. interesting. However, it does go to show that having slightly weird private integer types is actually totally workable, so the quote from the discussion might be meant as trolling, but it's less crazy than it sounds like.

rob74 3y ago
The difference is that (a) that bit in OCaml has a purpose, while disregarding 0x80..00 hasn't; and (b) I assume that it was in OCaml from the beginning, so it wouldn't break existing software in probably very interesting ways (hence the suggestion that this should be done only "in the privacy of their own bedrooms with new types", i.e. not for already-used types)...
- JKCalhoun 3y ago
  Yes, correct me if I'm wrong, but I thought the point was that 0x8000 is like negative zero and so of no utility, redundant. So let's make it useful.
  - mbel 3y ago
    It's not. 0x8000 is the smallest (-32,768) integer that can be represented with 16-bits and two's complement.
    - taeric 3y ago
      Yeah, I think it is funny that in a standard binary, it would replace negative zero and makes some sense. In two's complement, it replaces the minimum value. Fair that sentinel value is sentinel value, I suppose. But it is not like it is not a known and unique number in that encoding.

gregfjohnson 3y ago

Here is my favorite example of errors due to overflow: std::vector<int> vec; // test for sorted.. bool sorted = true; for (size_t i = 0; i < vec.size() - 1ULL; ++i) if (vec[i] > vec[i+1]) { sorted = false; break; } I believe the google c++ style guide rues the selection of unsigned integers as the return type of size() in the standard library for reasons like the above. Personally, my preferred behavior would be to have a compiler flag that could be used to enable a trap if unsigned arithmetic resulted in wrap-around, as in the above case when the vector is of length zero.

planede 3y ago
> Personally, my preferred behavior would be to have a compiler flag that could be used to enable a trap if unsigned arithmetic resulted in wrap-around, as in the above case when the vector is of length zero. That probably has the potential of having too many false positives. It's also very non-confroming, so I see why compiler vendors would be reluctant to add such a flag.
jcelerier 3y ago
> compiler flag that could be used to enable a trap if unsigned arithmetic resulted in wrap-around, as in the above case when the vector is of length zero. I mean.. this is exactly what -fsanitize=integer does in clang. I never saw a signed overflow UB, but how many "perfectly defined" yet horrendously wrong cases like this one this sanitizer has helped me find...
- gregfjohnson 3y ago
  Thanks so much - I was unaware of this clang flag. I just confirmed, it does exactly what I was hoping for! I suggested that this be an optional flag, not the default behavior. I could see using it for unit-test/static-analysis builds where performance is not the main concern. (I have not looked at the generated assembly or done a performance comparison, but it might be that the -fsanitize=integer flag would slow the generated code down.)
  - 3y ago

adrian_b 3y ago

In the past I have also been tempted by this idea that perhaps it would be better to redefine the current INT_MIN to be a NaN. Nevertheless, after thinking more about it, my conclusion was that this is not useful. The strongest argument in favor of it is that then an optional integer needs only the same size as an integer. Against this argument is the fact that in decades of programming I have never encountered the need for an optional integer type which needs for its base integer type all possible values. What I have encountered very frequently were optional integer types whose base integer type should have been defined as an integer interval a.k.a. integer range, like it is possible in languages like Ada or Pascal. For such optional integers with the valid values restricted to an interval, the optional type does not require extra storage over the base type, because the NaN can be represented by any value outside the permissible interval. The second argument for redefining INT_MIN to be a NaN is that this eliminates the possibility of overflows in several integer functions, like absolute value and negation. This argument is weak, because overflows can still happen in the more frequent arithmetic operations, so most non-trivial programs must still provide means to handle such exceptional cases. Moreover, the exceptions are avoided in absolute value and the like, by still having a (possibly implicit, i.e. inserted by the compiler) check that an integer value is not a NaN, somewhere before the code that uses negation, divide by -1, etc., perhaps in the invoking function, not in the invoked function to which integer arguments are passed, so this in the best case replaces multiple checks interspersed with the operations with a single check in the beginning, at the origin of the integer data. On the other hand, implicit checks that an integer is not a NaN would have to be added after additions and the like. The same is available now, in much of the code where integer overflows are possible one can check the range of the input integer data somewhere in the beginning, verifying that there are no values that can result in an overflow, avoiding further checks at each operation. The redefining of INT_MIN to be a NaN could help by relying on implicit checks added by a compiler in a few cases, but most expressions contain additions, subtractions and multiplications, so the program must still rely either on the compiler adding implicit overflow trap checks after each operation, for which adding the integer NaN does not give any improvements, or in the programmer writing explicit range checks that depend on the expressions that are computed, and for the majority of the expressions the explicit checks would still be needed.

tialaramex 3y ago

This is what nook:Balanced{I8,I16,I32,I64} are for. https://crates.io/crates/nook https://crates.io/crates/nook Of course today in Rust we're not allowed to bless such types for ourselves, this is reserved to the standard library (core::num::NonZeroU32 is a 4-byte unsigned integer which can't be zero for example) because it's relying on a nasty permanently unstable compiler-only feature to say "Hey, not all possible representations the right size for this type are valid". Rust has one very obvious set of types with such a niche, the references &T, but it also has not only the particular custom integers NonZero{U8,U16,U32,U64,I8,I16,I32,I64} and the Non-null pointers, but OS specific types (for Unix file descriptors, and Windows handles respectively) and of course char, it is 4 bytes but Unicode is explicitly limited to far fewer values, so that's a niche too. But today making more is not allowed in stable Rust, so while my nook crate is an interesting curiosity (and some day I'll implement integer math traits etc.) it cannot be stabilised and I was persuaded that the path forward is a whole lot of work to deliver the Pattern Types feature which can do this stably.

kibwen 3y ago
> permanently unstable compiler-only feature Arbitrary niches aren't intended to be permanently unstable (at least not in the sense of explicit implementation details like lang items and intrinsics), people have expressed a desire to stabilize them for years (as discussed during the original nonzero int types RFC). If something has changed in that regard, I'd appreciate a link to a discussion.
- tialaramex 3y ago
  The niche concept isn't permanently unstable, but the present mechanism is. Today the only way to make such a type is to use the magic attributes #[rustc_nonnull_optimization_guaranteed] #[rustc_layout_scalar_valid_range_start] and #[rustc_layout_scalar_valid_range_end] As their names hint, these are permanently unstable compiler-only type hints. I asked that some means be found to stabilize some equivalent hint (presumably with a name that doesn't look like a compiler-only feature) in one of the long series of tickets spawned after 3334 and I was persuaded that this is a terrible idea and won't happen. Instead the proposed path forward is (at least was then) Pattern Types. Build at least an MVP of the full blown Pattern Types feature instead of a custom attribute.

hoseja 3y ago

None of signed integer representations are very good, each has severe drawbacks.

flohofwoe 3y ago

At that point, why not introduce special i63 and u63 types and use the hidden bit 63 as 'soft carry flag' to detect over/undeflow. 63 bits of integer range ought to be enough for anyone ;) (as soon as bit 63 is set, the number would be in 'overflow state', but at the same time the lower 63 bits would preserve the wrap-around value in case that's useful). On the other hand, compilers are already free to check the CPU carry flag bit and trap on it. Those flag bits are just not exposed to programming languages (which IMHO is a serious 'dissonance' between assembly and high level languages), also CPU flags can't be carried around with their associated result value and go 'viral' like NaNs (but whether that's even useful instead of trapping immediately is another question).

jusuhi 3y ago
Because i63 won't help with 32 bit variables.
- flohofwoe 3y ago
  ...which is a bit of a weak reason when there are hardly any 32-bit CPUs around anymore though. Picking a narrower integer type makes sense in specific situations like tightly packed structs, but in that case it usually doesn't matter whether the integer range is 2^31 or 2^32, if you really need the extra bit of range it's usually ok to go to the next wider integer type.
  - jusuhi 3y ago
    Feel free to generalize my argument to i31 and i15. Also, look around you and realize that non-64-bit microprocessors outnumber 64-bit machines by orders of magnitude. There is more to the world than your laptop and smartphone. (Just within 1m of myself at this very moment I see 4 devices with a 32 bit microprocessor in them, and I'm sitting in a coffee shop reading a book. Well, and browsing HN now and then.)
    - flohofwoe 3y ago
      There's actually a better solution if you allow the compiler some wiggle room: Zig and C23 (and probably a couple other languages) support arbitrary width integers, so integer types like u15, i3, i1 or even u512 etc... are something entirely 'normal', and even useful in day-to-day coding when mixing signed and unsigned integer math (for instance Zig disallows to assign an unsigned integer to a signed integer of the same width, but it's perfectly fine to assign a 7-bit unsigned integer to an 8-bit signed integer). Down on the CPU such operations happen on the register width, and if the integer width exceeds the register width, are unrolled into a chain of op-with-carry instructions (same way we did 16- or 32-bit math back on 8-bit processors).

simiones 3y ago

Even if the current INT_MIN were redefined to be a NaN or a trap, that would do almost nothing to prevent signed integer overflow bugs. Sure, INT_MAX + 1 would be an error, but INT_MAX+2, INT_MAX+100 and so on would still be equal to INT_MIN + 1, INT_MIN + 99 etc. Besides, -fwrapv was basically the default in most C compilers (and probably C++ as well) before the last 10 years or so. Many large systems thus use it today as well (e.g. the Linux kernel, I believe).

trealira 3y ago
> Besides, -fwrapv was basically the default in most C compilers (and probably C++ as well) before the last 10 years or so. It seems like people were complaining as early as 2007. Richard Biener (who's linked in the thread link below) said that GCC 2.95.3, which came in 2001, optimized away signed overflow checks as well. https://gcc.gnu.org/bugzilla/show_bug.cgi?id=30475 https://gcc.gnu.org/bugzilla/show_bug.cgi?id=30475 --- > signed type overflow is undefined by the C standard, use unsigned int for the > addition or use -fwrapv You have GOT to be kidding? All kinds of security issues are caused by integer wraps, and you are just telling me that with gcc 4.1 and up I cannot test for them for signed data types any more?! You are missing the point here. There HAS to be a way to get around this. Existing software uses signed int and I can't just change it to unsigned int, but I still must be able to check for a wrap! There does not appear to be a work around I could do in the source code either! Do you expect me to cast it to unsigned, shift right by one, and then add or what?! PLEASE REVERT THIS CHANGE. This will create MAJOR SECURITY ISSUES in ALL MANNER OF CODE. I don't care if your language lawyers tell you gcc is right. THIS WILL CAUSE PEOPLE TO GET HACKED. I found this because one check to prevent people from getting hacked failed. THIS IS NOT A JOKE. FIX THIS! NOW!
- simiones 3y ago
  Thanks for looking into the history! Interesting to see that this wrong-headed behavior has now been around in GCC for longer than the status quo before. Other compilers are different though - MSVC only seems to have started optimizing around this in ~2016 or so, icc seems to have done something around this in 2020, and I'm sure many embedded compilers ignore it even today. I couldn't find anything definitive on clang, but given its history I assume it probably always enforced this mistake. I'd also note that several major C programs only work when signed integer overflow is defined: I mentioned Linux previously, but Python is another one. And Chrome and Firefox are considering enabling -fwrapv and equivalents.

silvestrov 3y ago

Rather than a trap representation I'd like a real trap, i.e. exception at runtime that can be caugth. Propagated NULL is useful in SQL but likely much less for integers as they are used as indexes. It is difficult to say when the "NaN" should result in a trap when doing pointer arithmetic using such numbers as the CPU does not have seperate pointer/integer data types. There are so many security problems from integer overflow. Also some easy way of checking an integer is in the range [0...n[ as a single instruction that traps if it is not.

drhagen 3y ago

R does this [1]. It is the sentinel that it uses internally to represent a missing value (i.e. NA) in integer arrays. Integer operations overflow to this value. [1] https://stackoverflow.com/a/56507840/1485877 https://stackoverflow.com/a/56507840/1485877

z29LiTp5qUC30n 3y ago

So they want symmetric complement of the ancient Knight Processor where there was NaN encoded so that divide by zero wasn't an exception but just a return NaN.

snickerbockers 3y ago

This person's mind is going to be blown when he learns about bitmasks.

planede 3y ago

A trap representation is not a NaN-like sentinel value. The post also didn't discuss the updated semantics of integer operations, but I assume it just simply shrinks the range of representable values by removing -2^(N-1), and operations with a resulting value that lie outside are still undefined. Having a NaN-like sentinel with is another option, with overflowing integer operations defaulting to that value instead, but that's not what is proposed here. The post does mention optional<int>, which could have the NaN-like sentinel (empty optional) by reusing the bit-pattern of the trap representation of the underlying int.

scotty79 3y ago

All is fun and games until your negative number is suprisingly off by one because somebody, somewhere didn't convert between two complement and "symmetrical" ints correctly

fargle 3y ago

this strikes me as a chesterton's fence situation - "what kind of weird nonsense is this 2's complement where it's asymmetric (yuck) and you can't negate -0x8000" i seriously doubt the folks who think this is a good idea know enough about the math and computer architecture to understand why in fact it's a terrible idea. - programming languages are abstractions. but (old joel) leaky ones sometimes. we don't like this, but you have to live with it. - in this case, the choice might be between reality-leaks such as "integers have limits", "the limits are asymmetric, leading to this negation pseudo-paradox" and a much worse leak such as "why does this spiffy safe integer type run 100,000 times slower than the weird C int" - actually math itself is a series of ever complicated abstractions. first counting numbers. then ZERO. then NEGATIVE numbers. ACK! now wait until you get to Fields and Rings and Galois Fields, which are very close to the concept of 2's complement integers. i believe that if ignoring the botched C standard that makes signed integer wraparound UB, "normal" 2's complement integers (and unsigned) form a finite ring. - so what? well even these fancy, and frankly, impenetrable math abstractions are just abstractions. they leak too and aren't "perfect" if you take into account the real universe which doesn't always match the perfect math. doesn't mean it isn't very useful. - these concepts can be used to reason about the behavior physical things, like the behavior of an array of flip-flops representing a 64 bit number and especially how you can create circuits and simplify them to do things that implement addition, multiplication, etc. - the problem with a sorta-1's-complement-without-two-zeros idea is it has none of these connections to grounded theoretical basis. so how do you simplify an adder? can you perform algebraic simplifications to it? what is the model for this thing? - symmetry is in the eye of the beholder. draw a 4-bit signed 2's complement drawing using "clock diagram". it works. now do it with 1's complement or this suggestion which is even worse with an odd, sometimes prime, number of nodes. - implementation: 2's complement is a very clever hardware technique that lets you interpret N bits as N digits of a binary number. each digit has weight 2^n: 1, 2, 4, 8, etc. except the last digit which has weight -2^n. this simple trick lets the signed and unsigned integers use the same addition, subtraction, and with minor processing, multiplication and division logic unchanged. it's very unlikely that you can implement the suggested scheme at even 1/10th the performance or cost. - and, yes, i think C really got it wrong calling "overflow" or wraparound UB. if it was defined to wrap, at least it would be theoretically analyzable. you'd still have overflow flaws, but that's provably impossible to avoid with finite sized integers of any design.