16 ms·

Signed integers are asymmetrical

136 points by zetalyrae 5y ago

SavantIdiot 5y ago
I find it interesting that so many responses are trying to dismiss this. I chatted with several programmer friends of mine and they all answered the question wrong (what is the abs(-128) in int8) and then got defensive and tried to play it off. Be honest, it is not an obvious gotcha. Don't get defensive if you didn't realize the implications of abs(-128) = -128 @int8.
jart 5y ago
Another interesting case is dividing INT_MIN by -1. On x86 at least, that will not only overflow, but raise an arithmetic exception too, just like divide by zero. So it's a useful trick for crashing code that tries to harden itself against SIGFPE being raised.
- bruce343434 5y ago
  Just tried this on x86-64, doesn't crash. #include <limits.h> #include <stdio.h> int main(int argc, char const *argv[]) { printf("%d", INT_MIN/(-1) == INT_MIN); return 0; }
  - jart 5y ago
    Give this a whirl: int Div(int a, int b) { return a / b; } int (*pDiv)(int, int) = Div; int main(int argc, char *argv[]) { printf("%d\n", pDiv(INT_MIN, -1)); return 0; }
- zetalyrae 5y ago
  Yes, for signed integer division of any bit-width this is the only case that results in overflow (division by zero is another exceptional case).
- benmmurphy 5y ago
  at some point in time you could crash solaris kernel by running a dtrace program that would divide INT_MIN by -1.
bumbledraven 5y ago
This issue could be even harder to detect with a generic Abs function. It would work on floats (I think?) and on almost all ints, but it would have edge case failures on certain ints.
- beached_whale 5y ago
  In C++ you would so something like if constexpr( std::is_unsigned_v<Number> ) { return x; } else { if( x >= 0 ) { return x; } if( x <= -std::numeric_limits<Number>::max( ) ) { // What do we return?? } return -x; } This comes up in parsing too. One often will harden against signed overflow by using an unsigned type and then multiplying the sign at the end. One needs to check for these kinds of things when the type is the biggest, like intmax_t(generally int64_t)
  - jepler 5y ago
    You can also (except this is awful!) work in the space of negative numbers through almost all of parsing and then, unless the sign is "-", negate the value just before returning it. However, having a base unsigned parsing routine and then doing signed conversion including application of unary +/- sign to the number at the very end allows sharing the most code.
    - beached_whale 5y ago
      The issue is that overflow on signed is UB. I can count final decimal places(ptr - start_ptr) to check if it is larger than the maximum digits allowed. This is cheap as the check is after the parse. Throw in a floor(log10( result )) == diff or something like that too.
sfblah 5y ago
This reminds me of an issue I had when pushing 64-bit integers from a C# stack down to JS. Lots of weird issues, which I finally tracked down to the fact that JS doesn't have full 64 bit precision for numbers. IIRC it's something like 56 bits.
- ohazi 5y ago
  53 bits. If this seems strange to anyone, it comes from the fact that all numbers in JS [1] are represented as double-precision floating point values. The bit format for doubles is a sign bit, 11 bits for the exponent, and 52 bits for the fraction. When storing integers in floats, you use an exponent of 1, and then stuff the integer into the fraction and sign bits. [1] I think bigint is a thing now?
  - dnautics 5y ago
    > When storing integers in floats, you use an exponent of 1, and then stuff the integer into the fraction and sign bits. Is this correct? I would have just guessed that JS stores integers as their equivalent float values, which is why above 53 bits, you stop being able to represent all whole numbers (but you can represent some whole numbers), unless JS-land has changed since I last checked in almost a decade ago.
    - ohazi 5y ago
      This is how you get the equivalent float value from an integer, assuming it fits within that 53 bit range. You're correct that you could pick a larger exponent at the expense of being able to store consecutive integers. Edit: Ignore this, I'm wrong.
      - dnautics 5y ago
        no, it is not. There is a "hidden" "one" bit, the fraction part "XXX..." of the IEEE 754 float represents 1.XXXX... to be multiplied by the (offset) exponent. The exponent for the integer 2 in f64 is different from the exponent section for the integer 1, this is easy to verify: const std=@import("std"); test "IEEE fp representation" { std.debug.print("\n{x}\n", .{@bitCast(u64, @as(f64, 1.0))}); std.debug.print("\n{x}\n", .{@bitCast(u64, @as(f64, 2.0))}); } gives 3ff0000000000000 4000000000000000 note that the fraction parts for both 1.0 and 2.0 are entirely zero, as they are powers of two times [1].00000000... The "hidden bit", while tricky and hard to understand, is probably one of the few truly good decisions that IEEE-754 comittee made out of a lot of kludgey compromises. Note that if they had done it the way you suggest, there would be degenerate representations for the same number, leading to a much smaller total possible representations for the same bitspace (this is a minor problem for most object-based "Decimal" number systems used for financial Txs -- you often need to use a specialized equality function instead of the language builtin), the "hidden one" ensures that every binary form has a uniquely represented value, not counting craziness with NaNs, and plus/minus zero, sigh.
saurik 5y ago
When I have built true absolute value operations--which has actually been pretty rare as I don't think you usually want "integers" for most computer work and are better off thinking in terms of finite fields instead of numbers whenever possible--I add a check that the result is actually non-negative (which is the kind of sanity check one would also want to write to verify you don't lose precision, saturate, or overflow in other "I am using these as numbers instead of a finite field" cases); or, if I am working with a number I know to be negative, sometimes I go with "the additive inverse wasn't the number itself", as in this code: https://github.com/OrchidTechnologies/orchid/blob/be5cc32a1649e699509bdd0514067d36cadc6dcd/lot-ethereum/lottery1.sol#L137 https://github.com/OrchidTechnologies/orchid/blob/be5cc32a16...
- dataflow 5y ago
  Bear in mind the absolute value is a red herring, the problems is negating a signed number, which is extremely common, and hardly anyone guards against that.
  - saurik 5y ago
    Well, nor do most people guard against absolute value failing, even inside their implementation: most people are simply wrong... that said, I also think matter-of-factly "negating" a signed number--rather than asking for the additive inverse of a field element (in which case -128 is the correct answer for -128 as when you later go to add it to another number it will have the correct behavior even if it doesn't look like it makes sense if you pretend it is a number)--is also usually a mistake ;P.
- Hermitian909 5y ago
  > finite fields instead of numbers whenever possible A nitpick: 32 or 64 bit integers are not finite fields. One of the finite field axioms is that any non-zero number must have a multiplicative inverse, which 2 does not have. They are, however, commutative rings.
  - Sniffnoy 5y ago
nyanpasu64 5y ago
I'm still convinced that C made the wrong decision to have abs(int) return signed int. Returning unsigned int would've been more semantically accurate, as well as eliminating a source of UB. At least Rust has unsigned_abs() now.
- dataflow 5y ago
  I think that would've only helped a little bit. I imagine most instances of this problem don't occur in abs() (which is just an illustration of the underlying problem), but when people perform simple negation.
- User23 5y ago
  The decision is so (apparently) obviously wrong that I'd really like to know what the decision process was. My first guess is that it involved some kind of architectural peculiarity of the PDP11.
  - bsder 5y ago
    1) Only "Two's Complement" signed arithmetic is asymmetric. One's Complement arithmetic wasn't uncommon on computers of the era and is fully symmetric. And, I believe that a PDP-7 uses one's complement. 2) "unsigned" didn't get implemented until about 5 years after C was initially implemented.
  - kevin_thibedeau 5y ago
    fabs() returns a signed result so abs() mirrors its behavior. Also if you're taking an absolute value, you're working in close proximity to negative numbers and risk accidentally performing subsequent operations on mixed types that cause an implicit cast from signed to unsigned. C's integer promotion rules allow this to happen.
  - zarzavat 5y ago
    If abs() returned unsigned then an expression such as -abs(x) would be surprising and wrong.
- jepler 5y ago
CalChris 5y ago
There is no absolute value for -128 (or 0xff) in the range of int8_t because 128 is not in 0..127. The error is not the logic or the compiler but rather the return type which should be (at least) int16_t. Indeed simply changing the return to int16_t gives abs(-128) = 128 abs(-127) = 127 abs( 0) = 0 abs( 126) = 126 abs( 127) = 127
- chrisseaton 5y ago
  Does the type flow back from the return type to the negation operator? I had no idea C worked like that! I would have assumed -x was the same type as x and then it was converted for the wider return type.
  - skitter 5y ago
    I believe x gets promoted to int, negated and then narrowed to the return type.
    - CalChris 5y ago
      That is what the LLVM IR says happens: https://godbolt.org/z/4aexEK3aE https://godbolt.org/z/4aexEK3aE
  - caf 5y ago
    Arithmetic operations are never done in a type narrower than int. int8_t is necessarily narrower than int (int must be able to represent at least the range -32767..32767), so in -x the x is promoted to int, then negated.
  - deleted 5y ago
    [deleted]
- nabla9 5y ago
  It just moves the problem. You can keep pushing the problem up to int64_t, but it does not go away. abs(-9223372036854775808) = -9223372036854775808 abs(-9223372036854775807) = 9223372036854775807 abs( 0) = 0 abs( 9223372036854775806) = 9223372036854775806 abs( 9223372036854775807) = 9223372036854775807
addaon 5y ago
Unsigned integers are also, trivially, asymmetrical. Floats are symmetrical at the cost of redundant encodings. Fundamentally a binary representation of b bits can support 2^b values. 2^b is even, and any symmetric range that includes zero has an odd number of distinct values, so a binary representation must either be asymmetric, contain undefined values, or contain redundant encodings (e.g. negative zero).
- manwe150 5y ago
  Floats could have had NaN occupy that encoding slot to balance against zero, but chose to instead add other complication and redundant encodings.
- unholiness 5y ago
  Floats still have an issue for this particular piece of code though! abs(-0) would return -0
  - kps 5y ago
    IEEE754 specifies that abs(−0) is 0 (positive). (If your machine doesn't use IEEE754, I'd love to hear more about your project.)
    - jsrcout 5y ago
      Some coworkers had to deal with MIL-STD-1750A [0] floating point recently. None of us had ever heard of it. They were talking to some pretty old HW. [0] https://en.wikipedia.org/wiki/MIL-STD-1750A https://en.wikipedia.org/wiki/MIL-STD-1750A
      - hoseja 5y ago
        Wow, lot of famous spacecraft using that.
    - Sniffnoy 5y ago
      The commenter above you isn't talking about IEEE754's abs() function, but rather the code from the OP, except applied to floats rather than ints.
champtar 5y ago
Discovered that abs can return negative value in Java running Findbugs some year ago, it blew my mind how booby trapped language can be.
- spc476 5y ago
  You should instead say "it blew my mind how booby trapped CPUs can be."
emerged 5y ago
Blame the concept of zero for making things odd. Edit: what idiot downvotes this?
- adolph 5y ago
  Underrated comment. Since zero is even, is every number system with zero asymmetric? Also, the commonly used Common Era system for dates does not include a year zero, so it is symmetric. A year zero does not exist in the Anno Domini (AD) calendar year system commonly used to number years in the Gregorian calendar (nor in its predecessor, the Julian calendar); in this system, the year 1 BC is followed directly by year AD 1. However, there is a year zero in both the astronomical year numbering system (where it coincides with the Julian year 1 BC), and the ISO 8601:2004 system, the interchange standard for all calendar numbering systems, (where year zero coincides with the Gregorian year 1 BC; see conversion table). And there is a year zero in most Buddhist and Hindu calendars. https://en.wikipedia.org/wiki/Year_zero https://en.wikipedia.org/wiki/Year_zero
guerrilla 5y ago
By the way, in the glibc manual for abs, there is a note: Trying to take the absolute value of the most negative integer is not defined.
perl4ever 5y ago
This is why I like Ada, even though I haven't used it in 20 years.
- zetalyrae 5y ago
  I was surprised to discover that -ftrapv did nothing. So the obvious next step was to test on Ada, which I expected would catch this error on the first try.
zgs 5y ago
Nothing to see here, move along. 2's complement is negative biassed. 1's complement (unmentioned in the article) is zero biassed. Neither surprise me. Seriously, who cares? Very few of us. I'm one but this isn't a problem for almost everyone else.
- marginalia_nu 5y ago
  The remarkable thing is how many people seem to be working with computers without understanding how they work.
Const-me 5y ago
ARM NEON did it right. They have two sets of integer negate and absolute instruction, normal and saturating. For signed bytes, the saturating versions transform -128 into +127.
adrian_b 5y ago
The reason why this is not signaled as an error in C/C++ with -ftrapv is because of the implicit integer truncation on assignment/initialization, which does not give errors in C/C++. In C/C++, when -x is computed, x is promoted to int, so "-" does not overflow and "-ftrapv" does not matter. This would be harmless, except that "return -x" truncates the result to 8 bits, which overflows, but this truncation is not checked so it does not signal an overflow exception, as it should in a decent programming language. Had x been an "int", instead of an "int8_t", the error would have been caught in C/C++ with -ftrapv (when "-" is applied to INT_MIN), but "int16_t" would have also resulted in an error that is not caught, due to implicit unchecked truncation. While forbidding all implicit conversions is a serious mistake in the opposite direction, many of the implicit conversions that exist in C/C++ for historical reasons are extremely harmful and they should be avoided like the plague, i.e. the truncation of larger integers into smaller integers and also the implicit conversions of signed integers into unsigned integers.
Aardwolf 5y ago
Ternary computers wouldn't have this issue
KMag 5y ago
Note that this isn't just a gotcha when writing your own absolute value function. The code given in the example is also how java.Math.abs() works. In C++ std::abs(std::numeric_limits<int>::min()) is undefined behavior (not even implementation-defined: nasal flying simian warning!). Most importantly, the optimizer is allowed to make optimizations that are only safe if abs() only returns non-negative values, but abs(INT_MIN) can also return a negative value (or trap to the kernel/SIGFPE/SIGBUS/etc. on some exotic architecture). So, in C++ one might be tempted to get around this issue by writing: static inline int my_abs(int x) { const int result = abs(x); if (result < 0 /* WRONG! UB! */ ) {return numeric_limits<int>::max();} return result; } But the C/C++ optimizer is allowed to optimize away your conditional branch. You need to check for INT_MIN before calling abs() if you want to guarantee the optimizer won't thwart you. More crazily, if the C/C++ optimizer discovers that some conditional branch is always conditioned on undefined behavior, it can just optimize away the branch, or even both sides of an if-else. static const int x = std::numeric_limits<int>::min(); void f() { puts("Before\n"); if (abs(x) >= 0) { puts("Expected\n"); } else { puts("Unexpected\n"); } puts("After\n"); } The optimizer is allowed to determine that neither the if nor the else ever executes and optimize f() to { puts("Before\n"); puts("After\n");} When I was at Google, Michael Chastain was telling me about one of the oddest bugs he helped debug (super helpful and knowledgeable guy, btw, one of the few people trusted with code ownership of the root of the monorepo). It was basically the above, but the UB was related to static initialization order of floating point variables. static double y = 22.0; static double x = y / 7.0; // Uh-oh... depends on floating point static init order void f() { if (x > M_PI) { ... } else { ... } } When my plan for world domination succeeds, one of my first acts as World Emperor will be to appoint a commission to change a lot of this undefined behavior into implementation-defined behavior.
deleted 5y ago
[deleted]
junon 5y ago
Seems like there's a weird error in the article that is obvious and kind of confuses me a bit. In the first example, the branch is `>= 0` but then in the "examples" second, the second part, it's `> 0`. Which is it? Either way, neat point to be made here. I'm surprised -ftrapv doesn't catch it.
- zetalyrae 5y ago
  Thanks for catching this! Pushed a fix: https://github.com/eudoxia0/eudoxia0.github.io/commit/dac9976432705ab19d975816b70f2279fd9a02cd https://github.com/eudoxia0/eudoxia0.github.io/commit/dac997...
fanf2 5y ago
My favourite integer run-time error is -128/-1 (eg for int8_t) because even code that is careful to avoid division by zero will often miss this case.
dsQTbR7Y5mRHnZv 5y ago
Decided to try in rust to test the behavior [0]: fn absolute(n: i8) -> i8 { if n >= 0 { n } else { -n } } fn main() { let nums = [i8::MIN, i8::MIN + 1, 0, i8::MAX - 1, i8::MAX]; for num in nums { println!("{}", absolute(num)); } } Seems to cause a runtime error: Compiling playground v0.0.1 (/playground) Finished dev [unoptimized + debuginfo] target(s) in 3.57s Running `target/debug/playground` thread 'main' panicked at 'attempt to negate with overflow', src/main.rs:2:27 note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace [0] https://play.rust-lang.org/?version=stable&mode=debug&edition=2021&gist=73976b255a748c62749c691183bb14ec https://play.rust-lang.org/?version=stable&mode=debug&editio...
- tialaramex 5y ago
  That's correct. Rust provides four versions of fundamental arithmetic for the integer types: * Checked where you get Some(answer) or None * Overflowing where you get (answer,false) or (overflowed_answer,true) * Saturating where you get answer or the closest of type:::MIN and type::MAX to the correct answer * Wrapping where the number line wraps around at the end If you don't pick which you wanted, but then you do something that's poorly defined a debug build will panic, whereas a production build wraps. The panic in debug is to encourage you to actually decide which of the four operations you meant and write that.
lonelygirl15a 5y ago
Signed integers are symmetrical on architectures like the Sperry Univac 1100/2200 and derivatives (still available from Unisys, I believe) which use ones complement, and therefore have both positive and negative zero.

136 points by zetalyrae 5y ago

I find it interesting that so many responses are trying to dismiss this. I chatted with several programmer friends of mine and they all answered the question wrong (what is the abs(-128) in int8) and then got defensive and tried to play it off. Be honest, it is not an obvious gotcha. Don't get defensive if you didn't realize the implications of abs(-128) = -128 @int8.

jart 5y ago

Another interesting case is dividing INT_MIN by -1. On x86 at least, that will not only overflow, but raise an arithmetic exception too, just like divide by zero. So it's a useful trick for crashing code that tries to harden itself against SIGFPE being raised.

bruce343434 5y ago
Just tried this on x86-64, doesn't crash. #include <limits.h> #include <stdio.h> int main(int argc, char const *argv[]) { printf("%d", INT_MIN/(-1) == INT_MIN); return 0; }
- jart 5y ago
  Give this a whirl: int Div(int a, int b) { return a / b; } int (*pDiv)(int, int) = Div; int main(int argc, char *argv[]) { printf("%d\n", pDiv(INT_MIN, -1)); return 0; }
zetalyrae 5y ago
Yes, for signed integer division of any bit-width this is the only case that results in overflow (division by zero is another exceptional case).
benmmurphy 5y ago
at some point in time you could crash solaris kernel by running a dtrace program that would divide INT_MIN by -1.

bumbledraven 5y ago

This issue could be even harder to detect with a generic Abs function. It would work on floats (I think?) and on almost all ints, but it would have edge case failures on certain ints.

beached_whale 5y ago
In C++ you would so something like if constexpr( std::is_unsigned_v<Number> ) { return x; } else { if( x >= 0 ) { return x; } if( x <= -std::numeric_limits<Number>::max( ) ) { // What do we return?? } return -x; } This comes up in parsing too. One often will harden against signed overflow by using an unsigned type and then multiplying the sign at the end. One needs to check for these kinds of things when the type is the biggest, like intmax_t(generally int64_t)
- jepler 5y ago
  You can also (except this is awful!) work in the space of negative numbers through almost all of parsing and then, unless the sign is "-", negate the value just before returning it. However, having a base unsigned parsing routine and then doing signed conversion including application of unary +/- sign to the number at the very end allows sharing the most code.
  - beached_whale 5y ago
    The issue is that overflow on signed is UB. I can count final decimal places(ptr - start_ptr) to check if it is larger than the maximum digits allowed. This is cheap as the check is after the parse. Throw in a floor(log10( result )) == diff or something like that too.

sfblah 5y ago

This reminds me of an issue I had when pushing 64-bit integers from a C# stack down to JS. Lots of weird issues, which I finally tracked down to the fact that JS doesn't have full 64 bit precision for numbers. IIRC it's something like 56 bits.

ohazi 5y ago
53 bits. If this seems strange to anyone, it comes from the fact that all numbers in JS [1] are represented as double-precision floating point values. The bit format for doubles is a sign bit, 11 bits for the exponent, and 52 bits for the fraction. When storing integers in floats, you use an exponent of 1, and then stuff the integer into the fraction and sign bits. [1] I think bigint is a thing now?
- dnautics 5y ago
  > When storing integers in floats, you use an exponent of 1, and then stuff the integer into the fraction and sign bits. Is this correct? I would have just guessed that JS stores integers as their equivalent float values, which is why above 53 bits, you stop being able to represent all whole numbers (but you can represent some whole numbers), unless JS-land has changed since I last checked in almost a decade ago.
  - ohazi 5y ago
    This is how you get the equivalent float value from an integer, assuming it fits within that 53 bit range. You're correct that you could pick a larger exponent at the expense of being able to store consecutive integers. Edit: Ignore this, I'm wrong.
    - dnautics 5y ago
      no, it is not. There is a "hidden" "one" bit, the fraction part "XXX..." of the IEEE 754 float represents 1.XXXX... to be multiplied by the (offset) exponent. The exponent for the integer 2 in f64 is different from the exponent section for the integer 1, this is easy to verify: const std=@import("std"); test "IEEE fp representation" { std.debug.print("\n{x}\n", .{@bitCast(u64, @as(f64, 1.0))}); std.debug.print("\n{x}\n", .{@bitCast(u64, @as(f64, 2.0))}); } gives 3ff0000000000000 4000000000000000 note that the fraction parts for both 1.0 and 2.0 are entirely zero, as they are powers of two times [1].00000000... The "hidden bit", while tricky and hard to understand, is probably one of the few truly good decisions that IEEE-754 comittee made out of a lot of kludgey compromises. Note that if they had done it the way you suggest, there would be degenerate representations for the same number, leading to a much smaller total possible representations for the same bitspace (this is a minor problem for most object-based "Decimal" number systems used for financial Txs -- you often need to use a specialized equality function instead of the language builtin), the "hidden one" ensures that every binary form has a uniquely represented value, not counting craziness with NaNs, and plus/minus zero, sigh.

saurik 5y ago

When I have built true absolute value operations--which has actually been pretty rare as I don't think you usually want "integers" for most computer work and are better off thinking in terms of finite fields instead of numbers whenever possible--I add a check that the result is actually non-negative (which is the kind of sanity check one would also want to write to verify you don't lose precision, saturate, or overflow in other "I am using these as numbers instead of a finite field" cases); or, if I am working with a number I know to be negative, sometimes I go with "the additive inverse wasn't the number itself", as in this code: https://github.com/OrchidTechnologies/orchid/blob/be5cc32a1649e699509bdd0514067d36cadc6dcd/lot-ethereum/lottery1.sol#L137 https://github.com/OrchidTechnologies/orchid/blob/be5cc32a16...

dataflow 5y ago
Bear in mind the absolute value is a red herring, the problems is negating a signed number, which is extremely common, and hardly anyone guards against that.
- saurik 5y ago
  Well, nor do most people guard against absolute value failing, even inside their implementation: most people are simply wrong... that said, I also think matter-of-factly "negating" a signed number--rather than asking for the additive inverse of a field element (in which case -128 is the correct answer for -128 as when you later go to add it to another number it will have the correct behavior even if it doesn't look like it makes sense if you pretend it is a number)--is also usually a mistake ;P.
Hermitian909 5y ago
> finite fields instead of numbers whenever possible A nitpick: 32 or 64 bit integers are not finite fields. One of the finite field axioms is that any non-zero number must have a multiplicative inverse, which 2 does not have. They are, however, commutative rings.
- Sniffnoy 5y ago

nyanpasu64 5y ago

I'm still convinced that C made the wrong decision to have abs(int) return signed int. Returning unsigned int would've been more semantically accurate, as well as eliminating a source of UB. At least Rust has unsigned_abs() now.

dataflow 5y ago
I think that would've only helped a little bit. I imagine most instances of this problem don't occur in abs() (which is just an illustration of the underlying problem), but when people perform simple negation.
User23 5y ago
The decision is so (apparently) obviously wrong that I'd really like to know what the decision process was. My first guess is that it involved some kind of architectural peculiarity of the PDP11.
- bsder 5y ago
  1) Only "Two's Complement" signed arithmetic is asymmetric. One's Complement arithmetic wasn't uncommon on computers of the era and is fully symmetric. And, I believe that a PDP-7 uses one's complement. 2) "unsigned" didn't get implemented until about 5 years after C was initially implemented.
- kevin_thibedeau 5y ago
  fabs() returns a signed result so abs() mirrors its behavior. Also if you're taking an absolute value, you're working in close proximity to negative numbers and risk accidentally performing subsequent operations on mixed types that cause an implicit cast from signed to unsigned. C's integer promotion rules allow this to happen.
- zarzavat 5y ago
  If abs() returned unsigned then an expression such as -abs(x) would be surprising and wrong.
jepler 5y ago

CalChris 5y ago

There is no absolute value for -128 (or 0xff) in the range of int8_t because 128 is not in 0..127. The error is not the logic or the compiler but rather the return type which should be (at least) int16_t. Indeed simply changing the return to int16_t gives abs(-128) = 128 abs(-127) = 127 abs( 0) = 0 abs( 126) = 126 abs( 127) = 127

chrisseaton 5y ago
Does the type flow back from the return type to the negation operator? I had no idea C worked like that! I would have assumed -x was the same type as x and then it was converted for the wider return type.
- skitter 5y ago
  I believe x gets promoted to int, negated and then narrowed to the return type.
  - CalChris 5y ago
    That is what the LLVM IR says happens: https://godbolt.org/z/4aexEK3aE https://godbolt.org/z/4aexEK3aE
- caf 5y ago
  Arithmetic operations are never done in a type narrower than int. int8_t is necessarily narrower than int (int must be able to represent at least the range -32767..32767), so in -x the x is promoted to int, then negated.
- deleted 5y ago
  [deleted]
nabla9 5y ago
It just moves the problem. You can keep pushing the problem up to int64_t, but it does not go away. abs(-9223372036854775808) = -9223372036854775808 abs(-9223372036854775807) = 9223372036854775807 abs( 0) = 0 abs( 9223372036854775806) = 9223372036854775806 abs( 9223372036854775807) = 9223372036854775807

addaon 5y ago

Unsigned integers are also, trivially, asymmetrical. Floats are symmetrical at the cost of redundant encodings. Fundamentally a binary representation of b bits can support 2^b values. 2^b is even, and any symmetric range that includes zero has an odd number of distinct values, so a binary representation must either be asymmetric, contain undefined values, or contain redundant encodings (e.g. negative zero).

manwe150 5y ago
Floats could have had NaN occupy that encoding slot to balance against zero, but chose to instead add other complication and redundant encodings.
unholiness 5y ago
Floats still have an issue for this particular piece of code though! abs(-0) would return -0
- kps 5y ago
  IEEE754 specifies that abs(−0) is 0 (positive). (If your machine doesn't use IEEE754, I'd love to hear more about your project.)
  - jsrcout 5y ago
    Some coworkers had to deal with MIL-STD-1750A [0] floating point recently. None of us had ever heard of it. They were talking to some pretty old HW. [0] https://en.wikipedia.org/wiki/MIL-STD-1750A https://en.wikipedia.org/wiki/MIL-STD-1750A
    - hoseja 5y ago
      Wow, lot of famous spacecraft using that.
  - Sniffnoy 5y ago
    The commenter above you isn't talking about IEEE754's abs() function, but rather the code from the OP, except applied to floats rather than ints.

champtar 5y ago

Discovered that abs can return negative value in Java running Findbugs some year ago, it blew my mind how booby trapped language can be.

spc476 5y ago
You should instead say "it blew my mind how booby trapped CPUs can be."

emerged 5y ago

Blame the concept of zero for making things odd. Edit: what idiot downvotes this?

adolph 5y ago
Underrated comment. Since zero is even, is every number system with zero asymmetric? Also, the commonly used Common Era system for dates does not include a year zero, so it is symmetric. A year zero does not exist in the Anno Domini (AD) calendar year system commonly used to number years in the Gregorian calendar (nor in its predecessor, the Julian calendar); in this system, the year 1 BC is followed directly by year AD 1. However, there is a year zero in both the astronomical year numbering system (where it coincides with the Julian year 1 BC), and the ISO 8601:2004 system, the interchange standard for all calendar numbering systems, (where year zero coincides with the Gregorian year 1 BC; see conversion table). And there is a year zero in most Buddhist and Hindu calendars. https://en.wikipedia.org/wiki/Year_zero https://en.wikipedia.org/wiki/Year_zero

guerrilla 5y ago

By the way, in the glibc manual for abs, there is a note: Trying to take the absolute value of the most negative integer is not defined.

perl4ever 5y ago

This is why I like Ada, even though I haven't used it in 20 years.

zetalyrae 5y ago
I was surprised to discover that -ftrapv did nothing. So the obvious next step was to test on Ada, which I expected would catch this error on the first try.

zgs 5y ago

Nothing to see here, move along. 2's complement is negative biassed. 1's complement (unmentioned in the article) is zero biassed. Neither surprise me. Seriously, who cares? Very few of us. I'm one but this isn't a problem for almost everyone else.

marginalia_nu 5y ago
The remarkable thing is how many people seem to be working with computers without understanding how they work.

Const-me 5y ago

ARM NEON did it right. They have two sets of integer negate and absolute instruction, normal and saturating. For signed bytes, the saturating versions transform -128 into +127.

adrian_b 5y ago

The reason why this is not signaled as an error in C/C++ with -ftrapv is because of the implicit integer truncation on assignment/initialization, which does not give errors in C/C++. In C/C++, when -x is computed, x is promoted to int, so "-" does not overflow and "-ftrapv" does not matter. This would be harmless, except that "return -x" truncates the result to 8 bits, which overflows, but this truncation is not checked so it does not signal an overflow exception, as it should in a decent programming language. Had x been an "int", instead of an "int8_t", the error would have been caught in C/C++ with -ftrapv (when "-" is applied to INT_MIN), but "int16_t" would have also resulted in an error that is not caught, due to implicit unchecked truncation. While forbidding all implicit conversions is a serious mistake in the opposite direction, many of the implicit conversions that exist in C/C++ for historical reasons are extremely harmful and they should be avoided like the plague, i.e. the truncation of larger integers into smaller integers and also the implicit conversions of signed integers into unsigned integers.

Aardwolf 5y ago

Ternary computers wouldn't have this issue

KMag 5y ago

Note that this isn't just a gotcha when writing your own absolute value function. The code given in the example is also how java.Math.abs() works. In C++ std::abs(std::numeric_limits<int>::min()) is undefined behavior (not even implementation-defined: nasal flying simian warning!). Most importantly, the optimizer is allowed to make optimizations that are only safe if abs() only returns non-negative values, but abs(INT_MIN) can also return a negative value (or trap to the kernel/SIGFPE/SIGBUS/etc. on some exotic architecture). So, in C++ one might be tempted to get around this issue by writing: static inline int my_abs(int x) { const int result = abs(x); if (result < 0 /* WRONG! UB! */ ) {return numeric_limits<int>::max();} return result; } But the C/C++ optimizer is allowed to optimize away your conditional branch. You need to check for INT_MIN before calling abs() if you want to guarantee the optimizer won't thwart you. More crazily, if the C/C++ optimizer discovers that some conditional branch is always conditioned on undefined behavior, it can just optimize away the branch, or even both sides of an if-else. static const int x = std::numeric_limits<int>::min(); void f() { puts("Before\n"); if (abs(x) >= 0) { puts("Expected\n"); } else { puts("Unexpected\n"); } puts("After\n"); } The optimizer is allowed to determine that neither the if nor the else ever executes and optimize f() to { puts("Before\n"); puts("After\n");} When I was at Google, Michael Chastain was telling me about one of the oddest bugs he helped debug (super helpful and knowledgeable guy, btw, one of the few people trusted with code ownership of the root of the monorepo). It was basically the above, but the UB was related to static initialization order of floating point variables. static double y = 22.0; static double x = y / 7.0; // Uh-oh... depends on floating point static init order void f() { if (x > M_PI) { ... } else { ... } } When my plan for world domination succeeds, one of my first acts as World Emperor will be to appoint a commission to change a lot of this undefined behavior into implementation-defined behavior.

deleted 5y ago

[deleted]

junon 5y ago

Seems like there's a weird error in the article that is obvious and kind of confuses me a bit. In the first example, the branch is `>= 0` but then in the "examples" second, the second part, it's `> 0`. Which is it? Either way, neat point to be made here. I'm surprised -ftrapv doesn't catch it.

zetalyrae 5y ago
Thanks for catching this! Pushed a fix: https://github.com/eudoxia0/eudoxia0.github.io/commit/dac9976432705ab19d975816b70f2279fd9a02cd https://github.com/eudoxia0/eudoxia0.github.io/commit/dac997...

fanf2 5y ago

My favourite integer run-time error is -128/-1 (eg for int8_t) because even code that is careful to avoid division by zero will often miss this case.

dsQTbR7Y5mRHnZv 5y ago

Decided to try in rust to test the behavior [0]: fn absolute(n: i8) -> i8 { if n >= 0 { n } else { -n } } fn main() { let nums = [i8::MIN, i8::MIN + 1, 0, i8::MAX - 1, i8::MAX]; for num in nums { println!("{}", absolute(num)); } } Seems to cause a runtime error: Compiling playground v0.0.1 (/playground) Finished dev [unoptimized + debuginfo] target(s) in 3.57s Running `target/debug/playground` thread 'main' panicked at 'attempt to negate with overflow', src/main.rs:2:27 note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace [0] https://play.rust-lang.org/?version=stable&mode=debug&edition=2021&gist=73976b255a748c62749c691183bb14ec https://play.rust-lang.org/?version=stable&mode=debug&editio...

tialaramex 5y ago
That's correct. Rust provides four versions of fundamental arithmetic for the integer types: * Checked where you get Some(answer) or None * Overflowing where you get (answer,false) or (overflowed_answer,true) * Saturating where you get answer or the closest of type:::MIN and type::MAX to the correct answer * Wrapping where the number line wraps around at the end If you don't pick which you wanted, but then you do something that's poorly defined a debug build will panic, whereas a production build wraps. The panic in debug is to encourage you to actually decide which of the four operations you meant and write that.

lonelygirl15a 5y ago

Signed integers are symmetrical on architectures like the Sperry Univac 1100/2200 and derivatives (still available from Unisys, I believe) which use ones complement, and therefore have both positive and negative zero.