位运算符查找小于在C(bitwise operators for finding less than

这是一个家庭作业需要我拿出一个函数来确定是否x < y如果是我必须返回1 ，只使用位运算符( ! ~ & ^ | + << >> ) 我只允许使用常量0 - 0xFF ，并假设一个32位整数。无回路，铸造等

我已经想通了的是，如果你是只检查说4位，你可以做x - y来确定x小于y 。如果x是8和y是9的结果将是1111为-1 。

int lessThan(int x, int y){
    int sub = x + (~y+1);

我感到困惑的是如何去现在的结果比较x ，以确定它确实是小于y 。

我一直在研究这篇文章在这里。

但我有点通过解决问题的方法混淆。我制定了换挡达到涂抹一点 ，但我困惑的你如何使用结果的值小于或大于比较。我只是在寻找一些指导和清晰度，不是一个解决方案，那不是我的意图。

Answer 1:

实施减法的想法是好的。

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位，它们的MSB（最高位显著）和所有其他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语句转换为一个单一的大丑逻辑表达式是“为读者的练习”。

Answer 2:

这里是我的尝试（编译的结果，X> Y 0然后，X <Y，然后1中，x == y，则1）：

((((x + ~y) >> 31) + 1))^1

Answer 3:

我认为它可以做achived如下：

XOR两个号码，这将使你的比特不同
获取的不同之最显著位，因为这一个会有所作为
检查大多数显著位属于更大的价值

码：

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);
}