我正在做CSAPP的datalab，isGreater函数。
这是描述

isGreater - if x > y  then return 1, else return 0
   Example: isGreater(4,5) = 0, isGreater(5,4) = 1
   Legal ops: ! ~ & ^ | + << >>
   Max ops: 24
   Rating: 3

x和y都是int类型。
所以我考虑模拟jg指令来实现它。这是我的代码

int isGreater(int x, int y)
{
    int yComplement = ~y + 1;
    int minusResult = x + yComplement;  // 0xffffffff
    int SF = (minusResult >> 31) & 0x1; // 1
    int ZF = !minusResult; // 0
    int xSign = (x >> 31) & 0x1; // 0 
    int ySign = (yComplement >> 31) & 0x1; // 1
    int OF = !(xSign ^ ySign) & (xSign ^ SF); // 0
    return !(OF ^ SF) & !ZF;
}

jg 指令需要 SF == OF 且 ZF == 0。
但它不能通过一个特殊情况，即x = 0x7fffffff(INT_MAX), y = 0x80000000(INT_MIN)。
我这样推论：
x + yComplement = 0xffffffff，因此 SF = 1，ZF = 0，因为 xSign != ySign，所以 OF 设置为 0。
那么，我的代码有什么问题，是我的OF设置操作错误吗？

您检测到加法溢出x + yComplement，而不是整体减法

-INT_MIN itself overflows in 2's complement; INT_MIN == -INT_MIN. This is the 2's complement anomaly https://en.wikipedia.org/wiki/Two%27s_complement#Most_negative_number¹.

您应该对任何负数（除了INT_MIN) minus INT_MIN。结果加法将有符号溢出。例如-10 + INT_MIN溢出。

http://teaching.idallen.com/dat2343/10f/notes/040_overflow.txt http://teaching.idallen.com/dat2343/10f/notes/040_overflow.txt有一个用于加法和减法的输入/输出符号表。溢出的情况是输入符号相反但结果符号匹配y.

      SUBTRACTION SIGN BITS  (for num1 - num2 = sum)
    num1sign num2sign sumsign
   ---------------------------
        0 0 0
        0 0 1
        0 1 0
 *OVER* 0 1 1 (subtracting a negative is the same as adding a positive)
 *OVER* 1 0 0 (subtracting a positive is the same as adding a negative)
        1 0 1
        1 1 0
        1 1 1

您可以直接将其与原始版本一起使用x and y，并且仅使用yComplement作为获得的一部分minusResult。调整你的逻辑以匹配这个真值表。

或者你可以使用int ySign = (~y) >> 31;并保留其余代码不变。 （使用 tmp 来保存~y所以你只需要执行一次操作，为此yComplement）。一个的反码 (~) 不会受到 2 补码异常的影响。

脚注1：符号/数值和补码有两种冗余方式来表示 0，而不是没有倒数的值。

有趣的事实：如果你创建一个整数绝对值函数，你应该考虑结果unsigned以避免这个问题。int不能代表绝对值INT_MIN.

效率提升：

如果你使用unsigned int，你不需要& 1移位后，因为逻辑移位不进行符号扩展。 （作为奖励，它可以避免 C 中的签名溢出未定义行为+: http://blog.llvm.org/2011/05/what-every-c-programmer-should-know.html http://blog.llvm.org/2011/05/what-every-c-programmer-should-know.html).

然后（如果你使用uint32_t, or sizeof(unsigned) * CHAR_BIT而不是 31) 您将获得 2 的补码比较的安全且可移植的实现。 （负数的有符号移位语义是在 C 中实现定义的。）我认为您正在使用 C 作为位操作的一种伪代码，并且对实际编写可移植实现不感兴趣，这很好。您的操作方式将在普通 CPU 上的普通编译器上运行。

或者你可以使用& 0x80000000将高位保留在适当的位置（但随后你必须左移你的!结果）。

这只是实验室的限制，你不能使用无符号或任何大于 0xff(255) 的常量

好的，所以您无权访问逻辑右移。不过，你最多需要一个&1。如果您只关心低位，但其余部分都是垃圾，那么处理数字是可以的。

你最终会做& !ZF，这是&0或&1. Thus, any high garbage in OF` 被擦除。

您还可以延迟>> 31直到将两个数字异或在一起之后。

这是一个有趣的问题，我想自己优化：

// untested, 13 operations
int isGreater_optimized(int x, int y)
{
    int not_y = ~y;
    
    int minus_y = not_y + 1;
    int sum = x + minus_y;

    int x_vs_y = x ^ y;       // high bit = 1 if they were opposite signs: OF is possible
    int x_vs_sum = x ^ sum;   // high bit = 1 if they were opposite signs: OF is possible

    int OF = (x_vs_y & x_vs_sum) >> 31;   // high bits hold garbage
    int SF = sum >> 31;

    int non_zero = !!sum;              // 0 or 1
    return (~(OF ^ SF)) & non_zero;      // high garbage is nuked by `& 1`
}

注意使用~代替!反转具有大量垃圾的值。

看起来将 OF 与 SF 分开计算仍然存在一些冗余，但实际上两次 sum 的异或并没有抵消。x ^ sum是一个输入&，然后我们与 sum 进行异或。

不过，我们甚至可以推迟移位，而且我通过避免额外的反转发现了更多的优化。这是 11 次操作

// replace 31 with  sizeof(int) * CHAR_BIT  if you want.  #include <limit.h>
// or use int32_t

int isGreater_optimized2(int x, int y)
{
    int not_y = ~y;

    int minus_y = not_y + 1;
    int sum = x + minus_y;
    int SF = sum;             // value in the high bit, rest are garbage

    int x_vs_y = x ^ y;       // high bit = 1 if they were opposite signs: OF is possible
    int x_vs_sum = x ^ sum;   // high bit = 1 if they were opposite signs: OF is possible
    int OF = x_vs_y & x_vs_sum;   // low bits hold garbage

    int less = (OF ^ SF);
    int ZF   = !sum;               // 0 or 1
    int le   = (less >> 31) & ZF;  // clears high garbage
    return  !le;                   // jg == jnle
}

我想知道是否有编译器可以通过这个手册比较并将其优化为cmp edi, esi/ setg al，但没有这样的运气：/我猜这不是他们寻找的模式，因为代码可以写成x > y倾向于be就这么写的 :P

但无论如何，这里是Godbolt 编译器浏览器上 gcc 和 clang 的 x86 asm 输出。 https://gcc.godbolt.org/#z:OYLghAFBqd5QCxAYwPYBMCmBRdBLAF1QCcAaPECAKxAEZSAbAQwDtRkBSAJgCFufSAZ1QBXYskwgA5HhYEA1HkEBxYpiYFMxAPqoADgTwBbPAC9M6CLIUAPUornyAngEoOABgCCHAOx8v8oEOCiyoBNpO8hwAzAAi8gB%2BTjH%2B3gFB1vImLCKCEVFx8qHhkfzytCkenkHB8oIiRgXxNlG8WbK5EZVeVTWZNtoAbnmlhS0cAKzYzik1QQD08/IIeMAI8gBGhE3ligBm8gQImJEA7lqY8vp6qIKEl3fALIIg8gDyAGKKgvI3gncbBiYXoZRwDYbaeqNGLNKJTOoNWaBRbLVbrLYKGG7PAHI4neTnNRXPR/e51VbPV6fb6/W4AoFVEGBTLUrEQcEjVoANnkHMhDRcBWwMWm0Qq0R4CyWKzWm0IPwQqAY6HkwCYxA2TGAwPSzMcAGUvlioUKRfIxd00tVQSFUCxtOZiKgdmBXWAoUi5l75Cj3FdiOUmfI1AQxCx5BAEhBWfDDS5BdweaF7Y7UJ6pajZWqNVrLkoiiIANYWTalLnuROB8uMnyxRleTJKVTqTQ6fSGEzmdBcKxg%2ByZVw11J9RzFfJYpKWoOZbKdUbxMelNri4c2hHQsatSWzkaWkcKQ07D0S71elGDJgMER58N4zPowj2NSCBTqy7ZzXa%2BvWvW2IacrFxnhZITzPaU0TlTFClofZDmOM4LmJUlNHJJ4XneL58z%2BekdR/Wo%2BRNQC4WmY9JWRcDZQxHYYJxOD8UJS5rluMlHkpDCaWwvBAVw/d2MA/9xy4HkCMRUCfSWBhUFOSCFSVFUP1zb9eKBf4dmjI1Yw%2BNwJWnRwAC0vkCLFXVI09vV9f1A11WogSCNkVJ%2BEUzTFBMhPkAykRRZAgXVBUIIUr9rJDMNAldBkxLM8ylioYAmixKgWAZHpayqKQXEYaQJikUgWGkdxstQaQAGF%2BDKYQxAkVoxWygg8rS9LCxAaIfAAOloLgJncaJoncABOAAWLr%2Btofr%2BoyqR%2Buyow6Hcdwcrq0hCqkbKXjm2qpHy9K4FgJA0CMPQ8CBMgKAgPaDqOlBmDYcs5r2Q7WxeCANgWrYWHVJxpFobK9qMTA5DeRKPo27KsCMVhgCBBb8DUZBDEGTAXmB0hMBsTBkBETRPuy6xMAYBaCGIYwsfSq72FK3hGC4l5IHS9s8DtRGAFoAHVLwYeRGbeaIVtEcRJFoEnMuy3KkaWmwAA4uUZrl%2BvkbzwfkLkWvcZWI1wQgSCq%2Bh5CK1B9sOrQtcFEreH4Gq6vjUhGq4XqWq4Hx2t6mWevLfquH6iZxsm0hptoWb5tF6QVpANaLdIbbEBQPXzq0chKDOg3iBAYBxfoO6GAeyhnqR173qx0gfr%2BggAYYIH8tIUHwchpHobRuGEYWlG0YxyQpC%2B8g5Fx/HCemtu0sYcGUHJgQGCp%2BBaYMenKSkTnuaEXmJDoQWpCygPy7FyXpdl4BkGQeRxbatX8CIANuDFexdf1o6qq4Y3h/N4HLeOJgsCTiAGqa6IWvLaIuR8dx%2Bo%2BAmL/WgXJ6B4wmsLBaS1g6h0fsvLgUDA7LVIOtTa6V4bEDuHaEA/UgA%3D