1

I am a beginner on CS and am using CSAPP to learn some knowledge.
(code below were built in 32-bit)
When I was writing my bits.c of CSAPP Lab datalab, I wrote a WRONG implementation in isLessOrEqual like this. It's a learning lab and the checker compiler limited available operators to ! ~ & ^ | + << >>.

int isLessOrEqual(int x, int y) {
  int a = y + (~x + 1);
  return !(a >> 31);
}

I know it's wrong because when x=0x80000000(TMIN) and y=0x7fffffff(TMAX), it will return 0.
But it was passed from btest (result = 1), when I inserted some printf to output some logs I got a strange result.

  if (x == 0x80000000 && y == 0x7fffffff) {
    printf("x = 0x%08x, y = 0x%08x, a = 0x%08x, a >> 31 = 0x%08x, a >> 31 & 1 = %d, result = %d, result & 1 = %d\n", x, y, a, a >> 31, a >> 31 & 1, !(a >> 31), !(a >> 31 & 1));
    if (a >> 31 == 0xffffffff)
      printf("a >> 31 = 0xffffffff, but !(a >> 31) = %d, and !!(a >> 31) = %d, !0xffffffff = %d\n", !(a >> 31), !!(a >> 31), !0xffffffff);
  }

Result from the log code.

x = 0x80000000, y = 0x7fffffff, a = 0xffffffff, a >> 31 = 0xffffffff, a >> 31 & 1 = 1, result = 1, result & 1 = 1
a >> 31 = 0xffffffff, but !(a >> 31) = 1, and !!(a >> 31) = 1, !0xffffffff = 0

I know a >> 31 = 0xffffffff and !0xffffffff = 0 are true because they fit my calculations.
But why did I get !(a >> 31) = 1 and !!(a >> 31) = 1, could anyone explain that please?

I copied all code to a new file and compiled it, it returned right 0.

UPDATE:
My friend analyzed the program with IDA and found the compiler optimized my code to that below directly.

_BOOL4 __cdecl isLessOrEqual(int a1, int a2)
{
  if ( a1 == 0x80000000 && a2 == 0x7FFFFFFF )
  {
    printf(
      "x = 0x%08x, y = 0x%08x, a = 0x%08x, a >> 31 = 0x%08x, a >> 31 & 1 = %d, result = %d, result & 1 = %d\n",
      0x80000000,
      0x7FFFFFFF,
      -1,
      -1,
      1,
      1,
      1);
    printf("a >> 31 = 0xffffffff, but !(a >> 31) = %d, and !!(a >> 31) = %d, !0xffffffff = %d\n", 1, 1, 0);
  }
  return a2 >= a1;
}

And I tested it with new file and compiled it with different flags.

#include <stdio.h>

int isLessOrEqual(int x, int y) {
  int a = y + (~x + 1);
  int result = !(a >> 31);
  if (x == 0x80000000 && y == 0x7fffffff) {
    printf("x = 0x%08x, y = 0x%08x, a = 0x%08x, a >> 31 = 0x%08x, a >> 31 & 1 = %d, result = %d, result & 1 = %d\n", x, y, a, a >> 31, a >> 31 & 1, !(a >> 31), !(a >> 31 & 1));
    if (a >> 31 == 0xffffffff)
      printf("a >> 31 = 0xffffffff, but !(a >> 31) = %d, and !!(a >> 31) = %d, !0xffffffff = %d\n", !(a >> 31), !!(a >> 31), !0xffffffff);
  }
  return result;
}

int main() {
    printf("%d\n", isLessOrEqual(0x80000000, 0x7fffffff));
}

Shell result:

***:~/workspace/$ gcc -o hello -m32 -O hello.c
***:~/workspace/$ ./hello
x = 0x80000000, y = 0x7fffffff, a = 0xffffffff, a >> 31 = 0xffffffff, a >> 31 & 1 = 1, result = 1, result & 1 = 1
a >> 31 = 0xffffffff, but !(a >> 31) = 1, and !!(a >> 31) = 1, !0xffffffff = 0
1
***:~/workspace/$ gcc -o hello -m32 hello.c
***:~/workspace/$ ./hello
x = 0x80000000, y = 0x7fffffff, a = 0xffffffff, a >> 31 = 0xffffffff, a >> 31 & 1 = 1, result = 0, result & 1 = 0
a >> 31 = 0xffffffff, but !(a >> 31) = 0, and !!(a >> 31) = 1, !0xffffffff = 0
0
Mark Rotteveel
  • 100,966
  • 191
  • 140
  • 197
Kuristra
  • 11
  • 2
  • 1
    Negating `INT_MIN` (on two's complement systems) has undefined behavior so I wouldn't spend so much time worrying about it. Better find a solution without undefined behavior instead. Fwiw, I get `but !(a >> 31) = 0, and !!(a >> 31) = 1` instead of `1` and `1`. – Ted Lyngmo Mar 12 '23 at 18:32
  • Related: [can't shift negative numbers to the right in c](https://stackoverflow.com/questions/49396937/cant-shift-negative-numbers-to-the-right-in-c). It is implementation defined. Also, please see the **Related** panel on the right. – Weather Vane Mar 12 '23 at 18:32
  • @TedLyngmo Thanks for your reply, I got ```0``` and ```1``` in my compiled new program with only this function and ```main```. I only got the wrong output in my CSAPP lab program so I was confused about it because I am learning 2's complement system with the lab. – Kuristra Mar 12 '23 at 18:46
  • @WeatherVane Thanks for your reply, I am just confused what it was doing and why did I get different output with same code in different places about that ```!(a >> 31)``` and ```!!(a >> 31)```. – Kuristra Mar 12 '23 at 18:49
  • @Ted Lyngmo, There no negation in that program – ikegami Mar 12 '23 at 18:49
  • 1
    isn't `(~x + 1)` negation? (two's complement) – Weather Vane Mar 12 '23 at 18:50
  • @Weather Vane, Not in the relevant sense. If the docs say it's UB to do `-x`, it doesn't mean it's UB to do `~x + 1`. It might be, but an entirely different analysis would be required to determine that. – ikegami Mar 12 '23 at 18:51
  • @Weather Vane, You were correct in saying there's implementation-defined behaviour, though. Specifically, `a >> 31` when `a` is negative is implementation-defined behaviour. – ikegami Mar 12 '23 at 18:53
  • @ikegami I suppose that `(~x + 1)` would also be *implementation defined*, since there is overflow with signed `INT_MIN`. – Weather Vane Mar 12 '23 at 18:53
  • 2
    tl,dr: Bit operations with signed values = headaches. Convert them to unsigned values. – ikegami Mar 12 '23 at 18:55
  • Indeed, I suggest `int isLessOrEqual(int x, int y)` body be rewritten as `return x <= y;` – Weather Vane Mar 12 '23 at 18:58
  • @WeatherVane Thanks for your reply, It's a learning lab and the checker compiler limited available operators to ```! ~ & ^ | + << >>```, and this error (both ```!(a>>31)``` and ```!!(a>>31)``` are 1) only occurs when writing code in lab file ```bits.c``` (right behaviour in other compiled programs), I don't know why. – Kuristra Mar 12 '23 at 19:02
  • @Weather Vane, They said it was a learning exercise concerning two's-complement. – ikegami Mar 12 '23 at 19:03
  • *"I copied all code to a new file and compiled it, it returned right 0."* You probably have some syntax errors in your code, so the new executable was not built and you were launching the same old program again and again. – 0___________ Mar 12 '23 at 19:07
  • @0___________ Thanks for your reply, I have tried ```make clean``` then ```make``` again or re-download all handout files to other folder, they have same behaviours (double 1). But I tried to download it to a Linux server just now, It run in right behaviour(0 and 1). So I am confused more about it. I am trying to copy my compied file to the server and check if it runs in wrong behaviour too. – Kuristra Mar 12 '23 at 19:17
  • 2
    *"So looks like It's a compiler issue?"* No, it is not. As the program behaviour is **UNDEFINED** the compiler is free to do whatever it wants. You **`must`** understand that if your code invokes UB - then that code is **invalid** – 0___________ Mar 12 '23 at 19:35
  • @0___________ Thanks for explaining that. Now I know what caused it and I will try to learn something about undefined behaviours. – Kuristra Mar 12 '23 at 19:47
  • 1
    @ikegami `~x + 1` (on a two's complement machine) is the negation I meant. It works for all `int`s except `INT_MIN` where the `+ 1` causes signed integer overflow and UB. – Ted Lyngmo Mar 12 '23 at 21:09

0 Answers0