这是一个家庭作业,需要我想出一个函数来确定x < y
,如果是,我必须返回1
,只使用位运算符( ! ~ & ^ | + << >> )
。我只被允许使用常量0 - 0xFF
,并假定为32位整数。没有循环、强制转换等。
我想出的是,如果你只检查比方说4位,你可以做x - y
来确定x
是否小于y
。如果x
为8
,y
为9
,则对于-1
,结果将为1111
。
int lessThan(int x, int y){
int sub = x + (~y+1);
我感到困惑的是,现在如何将结果与x
进行比较,以确定它确实低于y
。
我一直在研究这篇文章here。
但我对这种解决问题的方法感到有点困惑。我已经计算出了获得位涂抹的转换,但我不明白如何使用该结果来比较小于或大于的值。我只是在寻找一点指导和清晰度,而不是一个解决方案,这不是我的意图。
发布于 2018-05-25 23:25:57
我认为可以通过执行以下操作来实现:
或者这两个数字,这会给出不同的位,得到不同的最高有效位,因为如果最高有效位属于更大的值,difference
,,,
,
代码:
int less(int x, int y) {
//Get only diffed bits
int msb = x ^ y;
//Get first msb bit
msb |= (msb >> 1);
msb |= (msb >> 2);
msb |= (msb >> 4);
msb |= (msb >> 8);
msb |= (msb >> 16);
msb = msb - (msb >> 1);
//check if msb belongs to y;
return !((y & msb) ^ msb);
}
发布于 2018-01-19 00:48:10
实现减法的想法很好。
int sub = x + (~y+1);
从这里,你只需要检查sub
是否为负,即提取它的符号位。这就是技术难题出现的地方。
让我们假设x
和y
是无符号的32位整数。然后,减法的结果可以用一个带符号的33位整数来表示(检查它的最小值和最大值)。也就是说,直接使用表达式x + (~y+1)
没有任何帮助,因为它会溢出。
如果x
和y
是31位无符号数字会怎样?然后,x + (~y+1)
可以用一个32位带符号的数字表示,它的符号位告诉我们x
是否小于y
answer(x, y) := ((x + (~y+1)) >> 31) & 1
要将x
和y
从32位转换为31位,请将它们的最高有效位和所有其他31位分别放入不同的变量中:
msb_x = (x >> 31) & 1;
msb_y = (y >> 31) & 1;
x_without_msb = x << 1 >> 1;
y_without_msb = y << 1 >> 1;
然后考虑它们的MSB的4种可能组合:
if (msb_x == 0 && msb_y == 0)
return answer(x_without_msb, y_without_msb);
else if (msb_x == 1 && msb_y == 0)
return 0; // x is greater than y
else if (msb_x == 0 && msb_y == 1)
return 1; // x is smaller than y
else
return answer(x_without_msb, y_without_msb);
将所有这些if语句转换成一个大而丑陋的逻辑表达式是“读者的练习”。
发布于 2013-01-30 01:18:13
这是我的尝试(编译结果,x>y然后0,x
((((x + ~y) >> 31) + 1))^1
https://stackoverflow.com/questions/14588160
复制相似问题