模拟jg指令(datalab的isGreater)

simulate jg instruction(datalab's isGreater)

我正在做 CSAPP 的数据实验室,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 指令来实现 it.Here 我的代码

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设置操作有误吗?

假设二进制补码,INT_MIN 的绝对值不能表示为 int。因此,yComplement == y(即仍然为负),ySign1 而不是所需的 0

您可以像这样计算 y 的符号(在您的代码中尽可能少地更改):

int ySign = !((y >> 31) & 0x1);

如需更详细的分析和更优的备选方案,请查看

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

-INT_MIN本身在2的补码中溢出; INT_MIN == -INT_MIN。这是the 2's complement anomaly1.

您应该对任何负数(INT_MIN 除外)减去 INT_MIN 进行快速正溢出检测。生成的加法将有符号溢出。例如-10 + INT_MIN 溢出。

http://teaching.idallen.com/dat2343/10f/notes/040_overflow.txt 有一个 table 个 input/output 符号用于加减。溢出的情况是输入符号相反但结果符号匹配 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

您可以直接将其与原始 xy 一起使用,并且仅将 yComplement 用作获取 minusResult 的一部分。调整你的逻辑以符合这个事实 table.

或者您可以使用 int ySign = (~y) >> 31; 并且不修改其余代码。 (使用 tmp 保存 ~y,因此您只执行一次操作,为此和 yComplement)。 1 的反码 (~) 不受 2 的补码异常的影响。


脚注 1:sign/magnitude 和 1 的补码有两种多余的方式来表示 0,而不是一个没有倒数的值。

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


效率提升:

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

然后(如果您使用 uint32_tsizeof(unsigned) * CHAR_BIT 而不是 31),您将有一个安全且 portable 2 的补码比较的实现。 (负数的带符号移位语义是在 C 中实现定义的。)我认为您正在使用 C 作为一种用于位操作的伪代码,并且对实际编写 portable 实现不感兴趣,那很好。你做事的方式将适用于普通 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还有一些冗余,但实际上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 的代码往往会 变成 那样写 :P

但无论如何,这里是 the x86 asm output from gcc and clang on the Godbolt compiler explorer.