Find a value y such (x < y) == (-x > -y) will be false, when x is a signed integer and x=1?

Question

The question asks,

Let int x = 1, find a value for int y where the following statement will return false: (x < y) == (-x > -y)

I know the answer should be 4 bytes long (8 hex digits), but I don't know how to approach the question.

Think about the signed representation of an int as compared to an unsigned hex value... — dawg, Jul 02 '20 at 01:05
Possibly false when `y = INT_MIN` as `-INT_MIN` is UB, then anything may happen: Its true, its false, its [a talking muffin](https://www.goodbadjokes.com/jokes/two-muffins-were-sitting-in-an-oven-one-turned-to-the-other-and-said). — chux - Reinstate Monica, Jul 02 '20 at 03:13
Honestly, i would guess that INT_MIN is indeed the *intended* "correct" answer to this question, and whoever wrote it probably isn't too familiar with the concept of UB. So the question itself is flawed because it seems to assume a specific representation for negative values, and a specific defined behavior for signed overflow. — Felix G, Jul 02 '20 at 07:30

bolov · Accepted Answer · 2020-07-02T09:57:46.913

There isn't any value for y for which the expression is false. If we compile this:

int test(int y)
{
    int x = 1;
    
    return (x < y) == (-x > -y);
}

both gcc and clang with optimization enabled will generate this code:

test(int):
        mov     eax, 1
        ret

Any other answer that thinks is smart most likely uses overflow and is actually Undefined Behavior or misunderstands some C fundamentals.

Actually there are no values for either x or y for which the expression is false:

int test(int x, int y)
{
    return (x < y) == (-x > -y);
}

gives the same:

test(int, int):
        mov     eax, 1
        ret

It seems some people miss the implication and significance of the fact that the compilers transform the expression into return 1. This is proof that the compiler has definitely proven that there is no valid input for which the expression is false. Otherwise it would not have been allowed to do this optimization.

@mcleod_ideafix: `0x80000000` would cause a [signed overflow](https://en.wikipedia.org/wiki/Integer_overflow), which results in [undefined behavior](https://en.wikipedia.org/wiki/Undefined_behavior). — Andreas Wenzel, Jul 02 '20 at 01:19
The following question may help to explain why signed overflow causes undefined behavior: [Why is unsigned integer overflow defined behavior but signed integer overflow isn't?](https://stackoverflow.com/q/18195715/12149471) — Andreas Wenzel, Jul 02 '20 at 02:15

chux - Reinstate Monica · Answer 2 · 2020-07-02T03:18:16.777

0

Find a value y such (x < y) == (-x > -y) will be false, when x is a signed integer and x=1?

When unsigned y = 0.

int main(void) {
  int x = 1;
  unsigned y = 0;
  printf("%u\n", (x < y) == (-x > -y));
  return 0;
}

Output

Oops did not see the "find a value for int y (in hex)" until later.

Leave posted as wiki since it answer the title question, but gets disallowed in the details.

edited Jul 02 '20 at 03:18

answered Jul 02 '20 at 03:05

chux - Reinstate Monica

143,097
13
135
256

eddie kuo · Answer 3 · 2020-07-03T02:28:23.410

-1

The answer is INT_MIN == -INT_MIN, I think you have already known how it work.

But if you want do an experiment and feels bad for compiler optimization, you can use noclone attribute to prevent compiler do constant propgation, and noinline attribute let less() is a black box for main()

#include <limits.h>

__attribute__ ((noclone, noinline))
int less (int x, int y) {
  return x > y;
}

__attribute__ ((noclone, noinline))
int neg (int x) {
  return -x;
}

int main(void) {
  int x = 1, y = INT_MIN;
  return  less(x, y) == less(neg(y), neg(x));
}

edited Jul 03 '20 at 02:28

answered Jul 02 '20 at 07:21

eddie kuo

716
1
5
13

2

This answer can only be valid for a specific version of a specific compiler targeting a specific platform, and using a specific set of options. Change any of those variables and it might no longer work. – Felix G Jul 02 '20 at 07:40
3

In general, this answer is wrong for all the reasons noted many times already. Given `y = INT_MIN`, the use of `-y` can cause signed overflow and therefore undefined behavior. There's no way to handwave that away. – Andrew Henle Jul 02 '20 at 09:46
Thanks @Andrew Henle. I add `neg()` to make a black box for compiler to fix the mistake. – eddie kuo Jul 03 '20 at 02:30
Your addition of `neg()` fixes nothing. You still have `return -x`. If you pass your `neg()` function `INT_MIN`, it will try return `-INT_MIN`. Which is undefined behavior - ***AGAIN***. There's no such thing as a "black box" in software that can magically make undefined behavior disappear - the code does what the code does whether you bother to look inside the box or not.. And in this case, it's undefined behavior no matter how many functions – Andrew Henle Jul 03 '20 at 11:02
If compiler don't inline and not do cprop, compiler could not know the program would execute -INT_MIN – eddie kuo Jul 06 '20 at 05:24

score -2 · Answer 4 · answered Jul 02 '20 at 01:22

-2

If int is defined as 32 bit two-complement value, then value 0x80000000 will fail the comparison. The reason is that two-complement values has one more value in the negative side than in the positive side. Any positive value can be converted to negative, but not all negative values can be converted to positive.

So, for the above mentioned value, y and -y are actually the same value and the first comparison (x < y) will yield "false" where (-x > -y) will yield "true", making the whole expression "false".

But it wouldn't happen if, as in the answer from @bolov, the compiler optimizes the function.

answered Jul 02 '20 at 01:22

mcleod_ideafix

11,128
2
24
32

4

"then value 0x80000000 will fail the comparison" - I disagree with this statement. It is undefined what will happen in this case. The comparison may evaluate to true or false or the compiler may treat any code which leads to the signed overflow as unreachable, which allows it to be optimized away. That is the nature of [undefined behavior](https://en.wikipedia.org/wiki/Undefined_behavior). See [this excellent answer](https://stackoverflow.com/a/9452284/12149471) by Microsoft Blogger Raymond Chen for more information on what the compiler may do in the event of undefined behavior. – Andreas Wenzel Jul 02 '20 at 01:48
2

Yes with `0x80000000` we have Undefined Behavior. This answer is incorrect. – bolov Jul 02 '20 at 01:59
3

And bolov's answer already preemptively predicted this wrong answer: "Any other answer that thinks is smart most likely uses overflow and is actually Undefined Behavior or misunderstands some C fundamentals." – R.. GitHub STOP HELPING ICE Jul 02 '20 at 04:01

Find a value y such (x < y) == (-x > -y) will be false, when x is a signed integer and x=1?

4 Answers4