8

这是一个家庭作业，需要我想出一个函数来确定是否x < y，如果是，我必须返回1，只使用位运算符( ! ~ & ^ | + << >> )。我只被允许使用 constants 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。

我一直在这里检查这篇文章。

但是我对这种解决问题的方法有点困惑。我已经计算出移位以实现位涂抹，但我对如何使用该结果来比较小于或大于的值感到困惑。我只是在寻找一点指导和清晰度，而不是解决方案，这不是我的意图。

4

5 回答 5

3

我认为可以通过以下方式实现：

  1. 异或两个数字，这会给你不同的位
  2. 获取不同的最重要的位，因为这会有所作为
  3. 检查最重要的位是否属于更大的值

代码：

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-05-25T15:25:56.797 回答
1

实现减法的想法很好。

int sub = x + (~y+1);

从这里，您只需要检查是否sub为负，即提取其符号位。这就是技术难点出现的地方。

假设x和y是无符号的 32 位整数。然后减法的结果可以用一个有符号的 33 位整数表示（检查它的最小值和最大值以查看）。也就是说，x + (~y+1)直接使用表达式没有帮助，因为它会溢出。

如果是 31 位无符号数怎么办x？y那么，x + (~y+1)可以用一个 32 位的有符号数来表示，它的符号位告诉我们是否x小于y：

answer(x, y) := ((x + (~y+1)) >> 31) & 1

要将32 位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 语句转换为一个大而丑陋的逻辑表达式是“读者练习”。

于 2018-01-18T16:48:10.433 回答
0

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

((((x + ~y) >> 31) + 1))^1
于 2013-01-29T17:18:12.900 回答
0

只是想添加到这个讨论中，因为我不确定它是否已经被提及。这里的一些人提出了这一点

( x + ((~y) + 1)) >> 32) & 0x1

不适用于溢出条件。对于二进制补码，整数 x 和 y 相加的溢出条件是：

x > 0, y > 0, (x+y) < 0

x < 0, y < 0, (x+y) > 0

在这种情况下，我们将 x 和 (-y) 相加，并且还必须在确定 (xy)<0 之前检查溢出条件

long isLess(long x, long y) {
    long xs= (x>>63) & 0x1L; 
    long ys= (y>>63) & 0x1L;
    long s = x + (~y +1L);

    long ss= (s>>63) & 0x1L;

    /*
    //Code without SOP result for clarity
    if(xs & ~ys & ~ss) return 1;
    if(~xs & ys & ss)  return 0;

    return ss;
    */

    return (((xs | ~ys | ~ss) & (~xs | ys | ss)) & ss) |
           (((~xs & ys & ss) | (xs & ~ys & ~ss)) & ~ss);
}
于 2021-12-15T20:56:24.117 回答
-1

为了知道是否x < y，您可以简单地询问是否x - y < 0。

换句话说， 的结果的符号是什么x - y。

既然你说你要假设 32 位整数，以下将提供正确的结果：

((x - y) >> 31) & 0x1
于 2017-12-17T20:46:14.903 回答