我必须使用位处理来找到两个数字中的较大者.这些是相同的规则:
I have to find the greater of two numbers using bit manipulation. These are the rules for the same:
/* * isGreater - if x > y then return 1, else return 0 * Example: isGreater(4,5) = 0, isGreater(5,4) = 1 * Legal ops: ! ~ & ^ | + << >> * Max ops: 24 */这是我为此编写的代码:
This is the code I've written for this:
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<y */ int ydash=(~y)+0x01; int diff=x+ydash; int a=(~diff)+0x01; int b=a>>31; int c=b&0x01; return c; }我收到此错误:
错误:Test isGreater(-2147483648 [0x80000000]，2147483647 [0x7fffffff])失败... ...给出1 [0x1].应该为0 [0x0]
ERROR: Test isGreater(-2147483648[0x80000000],2147483647[0x7fffffff]) failed... ...Gives 1[0x1]. Should be 0[0x0]
允许使用unsigned int，但不能使用其他数据类型.我不确定这会有什么帮助.我该如何解决?
I'm allowed to use unsigned int, but no other data types. I'm not sure how that'd help though. How do I get around this?
推荐答案如果x = -2147483648和y = 2147483647，则x-y = -4,294,967,295(超出int的范围)，因此结果无法表示为变量，您将获得未定义的行为.
With x = -2147483648 and y = 2147483647 then x - y = -4,294,967,295 which is outside the range of int, hence the result cannot be represented in the variable and you got undefined behavior.
要克服这个问题，您需要使用比int宽的类型.因为只允许使用unsigned int，所以如果要使用更大的类型，则必须自己实现big int操作.您还可以使用另一种方式，例如单独检查溢出条件
To get over this you need to use a type wider than int. As you are only allowed to use unsigned int, you'll have to implement big int operations yourself if you want to use a bigger type. You can also use another way like checking the overflow condition separately
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; }如果不允许使用条件语句，则可以使用多路复用器将值多路复用
If you aren't allowed to use conditionals you can use a muxer to mux the values
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);