c - 模拟 jg 指令(datalab 的 isGreater)

Question

我在做 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 设置操作错误吗？

Answer 1

您在加法 x + yComplement 中检测到溢出, 而不是在整体减法 -INT_MIN本身在 2 的补码中溢出； INT_MIN == -INT_MIN .这是 the 2's complement anomaly 1.
您应该对任何负数(除 INT_MIN 外)减去 INT_MIN 进行快速正溢出检测.由此产生的加法将有符号溢出。例如-10 + INT_MIN溢出。
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 一起使用和 y ，并且只使用 yComplement作为获取 minusResult 的一部分.调整您的逻辑以匹配此真值表。
或者你可以使用 int ySign = (~y) >> 31;并保留其余代码不变 . (使用 tmp 来保存 ~y 所以你只做一次操作，对于这个和 yComplement )。一个的补码逆 ( ~ ) 不会受到 2 的补码异常的影响。

脚注 1 :符号/大小和补码有两种冗余方式来表示 0，而不是一个没有逆的值。
有趣的事实:如果你做一个整数绝对值函数，你应该考虑结果 unsigned为了避免这个问题。 int不能代表 INT_MIN的绝对值.

效率提升:
如果您使用 unsigned int ，你不需要 & 1移位后，因为逻辑移位不进行符号扩展。 (作为奖励，它可以避免 + : http://blog.llvm.org/2011/05/what-every-c-programmer-should-know.html 中的 C 签名溢出未定义行为)。
然后(如果您使用 uint32_t 或 sizeof(unsigned) * CHAR_BIT 而不是 31)您将拥有安全且可移植的 2 补码比较实现。 (负数的有符号移位语义是在 C 中实现定义的。)我认为您将 C 用作一种用于位操作的伪代码，并且对实际编写可移植实现不感兴趣，这很好。您的处理方式适用于普通 CPU 上的普通编译器。
或者您可以使用 & 0x80000000将高位保留在原位(但是您必须左移您的 ! 结果)。

It's just the lab's restriction, you can't use unsigned or any constant larger than 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`
}

注意使用 ~而不是 !反转具有高垃圾的值。
看起来与SF分开计算OF仍然存在一些冗余，但实际上两次求和的异或并没有抵消。 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 的代码倾向于这样写:P
但无论如何，这里是 the x86 asm output from gcc and clang on the Godbolt compiler explorer.