模拟jg指令(datalab的isGreater)

我正在做CSAPP的datalab,即isGreaterfunction。
这是描述

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本身溢出2的补码; INT_MIN == -INT_MIN 。 这是2的补码exception 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 

您可以直接使用原始xy ,并仅使用yComplement作为获取minusResult一部分。 调整逻辑以匹配此真值表。

或者你可以使用int ySign = (~y) >> 31; 并保持其余代码不被修改 。 (使用tmp来保持~y所以你只执行一次操作,为此和yComplement )。 一个补码逆( ~ )不会受到2的补码exception的影响。


脚注1 :符号/幅度和一个补码有两种冗余方式来表示0,而不是没有反向的值。

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


效率改进:

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

然后(如果你使用uint32_t ,或sizeof(unsigned) * CHAR_BIT而不是31)你就可以安全便携地实现2的补码比较。 (负数的带符号移位语义是在C中实现定义的。)我认为你使用C作为一种用于位操作的伪代码,并且对实际编写可移植实现不感兴趣,这很好。 你正在做事的方式将适用于普通CPU上的普通编译器。

或者你可以使用& 0x80000000将高位保留在原位(但是你必须离开你的!结果)。

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

好的,所以你没有逻辑右移的权限。 不过,你最多需要一个&1 。 可以使用数字,你所关心的只是低位,但其余的都是垃圾。

你最终做& !ZF ,它是&0或&1 . Thus, any high garbage in . Thus, any high garbage in OF`中的. Thus, any high garbage in都会被消除。

您也可以延迟>> 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时仍然存在一些冗余,但实际上两次的和的XOR不会抵消。 x ^ sum&的输入,之后我们与sum进行异或。

尽管如此,我们可以延迟转变,并且通过避免额外的反转我发现了一些更优化。 这是11次操作

 // replace 31 with sizeof(int) * CHAR_BIT if you want. #include  // 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

但无论如何,这是来自gb的x86 asm输出和Godbolt编译器浏览器上的clang。

假设两个补码, INT_MIN的绝对值不能表示为int 。 所以, yComplement == y (即仍为负数), ySign1而不是所需的0

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

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

有关更详细的分析和更优化的选择,请查看Peter Cordes的答案 。