用于查找小于的按位运算符
这是一个家庭作业，需要我想出一个函数来确定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。
但我对这种解决问题的方法感到有点困惑。我已经计算出了获得位涂抹的转换，但我不明白如何使用该结果来比较小于或大于的值。我只是在寻找一点指导和清晰度，而不是一个解决方案，这不是我的意图。
回答 5
Stack Overflow用户
发布于 2018-05-25 23:25:57
我认为可以通过执行以下操作来实现：
或者这两个数字，这会给出不同的位，得到不同的最高有效位，因为如果最高有效位属于更大的值，difference
- Check，
- ，
，，，
- ，
，
代码：
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);
}Stack Overflow用户
发布于 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语句转换成一个大而丑陋的逻辑表达式是“读者的练习”。
Stack Overflow用户
发布于 2013-01-30 01:18:13
这是我的尝试(编译结果，x>y然后0，x
((((x + ~y) >> 31) + 1))^1https://stackoverflow.com/questions/14588160
复制相似问题