isGreater按位C操作 – 两个数字中最大的一个
按位操作，我必须找到两个数字中最大的一个。 这些是相同的规则：
/* * isGreater - if x > y then return 1, else return 0 * Example: isGreater(4,5) = 0, isGreater(5,4) = 1 * Legal ops: ! ~ & ^ | + <> * Max ops: 24 */ 这是我为此编写的代码：
int isGreater(int x, int y) { /* to find greater, subtract y from x using 2's complement method. * then find 2's complement of the answer and shift right by 31 to give MSB * which is 1 if x>y and 0 if x>31; int c=b&0x01; return c; }
为此我收到此错误：
错误：测试isGreater（-2147483648 [0x80000000]，2147483647 [0x7fffffff]）失败…… …给出1 [0x1]。 应为0 [0x0]
我被允许使用unsigned int，但没有其他数据类型。 我不确定那会有多大帮助。 我该如何解决这个问题？
在这里，您可能不被允许使用if-else或任何控制语句。 但是你可以“构造”一些if-else-like语句。
int isGreater(int x, int y) { int sgnext_x = x >> 31; //sgnext_x = x >= 0 ? 00000000 : 11111111 int sgnext_y = y >> 31; int sgn_y = sgnext_y & 1; //sgn_y = y >= 0 ? 0 : 1 int minus = x + (~y + 1); // a - b = a + (~b+1) int sgn_minus =(minus >> 31) & 1; //A control-like statement. ((statement & a) | (!(statement | (b)))) //Returns a if statment = 11111111 //Returns (b&1) if statment = 00000000 int which = sgnext_x ^sgnext_y; int result = (!!(x^y)) & ((which & sgn_y) | (!(which | (sgn_minus)))); return result; }
对于x = -2147483648和y = 2147483647，则x – y = -4,294,967,295，这超出了int的范围，因此结果无法在变量中表示，并且您得到了未定义的行为。
要克服这个问题，你需要使用比int更宽的类型。 由于您只允许使用unsigned int，因此如果要使用更大的类型，则必须自己实现大型int操作。 您还可以使用其他方法，例如单独检查溢出条件
if ((x ^ y) & 0x80000000) // x and y have different sign { return (y >> 31) & 1; // return 1 if y is negative } else // x and y have the same sign, overflow never occurs { unsigned int xu = x, yu = y; unsigned int xmu = ~xu + 1U; unsigned int diffu = yu + xmu; return diffu >> 31; }
如果不允许使用条件，则可以使用复用器来复用值
unsigned int r1 = (y >> 31) & 1U; // 1st case unsigned int xu = x, yu = y; unsigned int xmu = ~xu + 1U; unsigned int diffu = yu + xmu; unsigned int r2 = diffu >> 31; // 2nd case unsigned int s = ((x ^ y) >> 31) & 1U; // s = 1 if x and y have different sign, 0 otherwise unsigned int mask = 0xFFFFFFFFU + s; return (r1 & ~mask) | (r2 & mask);
你提出的算法从根本上是行不通的，因为如果你减去，几乎所有可能的答案都可以是减法的结果，其中a < b和减法的结果，其中a >= b 。 所以基本上，结果并没有告诉你什么，除非它为零，那么你知道a == b 。
Hacker's Delight在第2.11章比较谓词中有这个答案：
x < y: (x & ~y) | ((x ^ ~y) & (x - y))
（ validation ）
你知道如何在加法方面实现减法，交换x和y也不应该是一个问题。 结果显示在符号位中。