2

我正在做一个家庭作业，我需要创建一个最多包含 24 个运算符的按位方法。我的代码有效……但我有 25 个操作员，一个太多了。谁能找到一种更有效的方法来编写一段代码？

 int isGreater(int x, int y)
    {
      int xSign = (x>>31);
      int ySign = (y>>31);
      int check1 = (xSign & ySign) | (~xSign & ~ySign);
      int same = !((( x + ((~y) + 1) )>>31) & 0x1);
      int check2 = (check1 & same) | (~check1 & !xSign);
      int equal = ((!(x ^ y))<<31)>>31;
      return 0 | (~equal & check2);
    }
4

6 回答 6

6

尝试更改此行：

int check1 = (xSign & ySign) | (~xSign & ~ySign);

为了这：

int check1 = (xSign & ySign) | ~(xSign | ySign);

那是少了一位操作员。

于 2012-04-14T04:51:42.970 回答
4

check1只是一个xnor. 你为什么不替换这个：

  int check1 = (xSign & ySign) | (~xSign & ~ySign);

有了这个：

  int check1 = ~(xSign ^ ySign);

你的版本有 5 个位运算符，我的有 2 个。

请注意，如果您使用此代码，您的代码会更美观：

  int check1 = !(xSign ^ ySign);

也就是说，逻辑否定而不是按位否定，但不要担心正确性，因为最后你无论如何都会取消所有高位。

于 2012-04-14T04:59:12.937 回答
2

这一行：

return 0 | (~equal & check2);

可以简化为：

return (~equal & check2);

（按位or与0没有任何效果）

于 2012-04-14T04:54:01.143 回答
2

假设ints 是 32 位宽，您可以替换它：

  int equal = ((!(x ^ y))<<31)>>31;

有了这个：

  int equal = ((!(x ^ y)) & 0x1;

再救自己一个。

于 2012-04-14T05:02:51.543 回答
1

INT_MIN我在 C 中提出了这个相对较短的解决方案，它可以处理从到的整个整数范围INT_MAX。

它期望有符号整数实现为 2 的补码，并且它期望有符号溢出不会产生不良副作用（已知会导致未定义的行为）。

#include <stdio.h>
#include <limits.h>

int isGreater(int x, int y)
{
  // "x > y" is equivalent to "!(x <= y)",
  // which is equivalent to "!(y >= x)",
  // which is equivalent to "!(y - x >= 0)".
  int nx = ~x + 1; // nx = -x (in 2's complement integer math)
  int r = y + nx;  // r = y - x (ultimately, we're interested in the sign of r,
                   // whether r is negative or not)

  nx ^= nx & x;    // nx contains correct sign of -x (correct for x=INT_MIN too)

  // r has the wrong sign if there's been an overflow in r = y + nx.
  // It (the r's sign) has to be inverted in that case.

  // An overflow occurs when the addends (-x and y) have the same sign
  // (both are negative or both are non-negative) and their sum's (r's) sign
  // is the opposite of the addends' sign.
  r ^= ~(nx ^ y) & (nx ^ r); // correcting the sign of r = y - x

  r >>= (CHAR_BIT * sizeof(int) - 1); // shifting by a compile-time constant

  return r & 1; // return the sign of y - x
}

int testDataSigned[] =
{
  INT_MIN,
  INT_MIN + 1,
  -1,
  0,
  1,
  INT_MAX - 1,
  INT_MAX
};

int main(void)
{
  int i, j;

  for (j = 0; j < sizeof(testDataSigned)/sizeof(testDataSigned[0]); j++)
    for (i = 0; i < sizeof(testDataSigned)/sizeof(testDataSigned[0]); i++)
      printf("%d %s %d\n",
             testDataSigned[j],
             ">\0<=" + 2*!isGreater(testDataSigned[j], testDataSigned[i]),
             testDataSigned[i]);

  return 0;
}

输出：

-2147483648 <= -2147483648
-2147483648 <= -2147483647
-2147483648 <= -1
-2147483648 <= 0
-2147483648 <= 1
-2147483648 <= 2147483646
-2147483648 <= 2147483647
-2147483647 > -2147483648
-2147483647 <= -2147483647
-2147483647 <= -1
-2147483647 <= 0
-2147483647 <= 1
-2147483647 <= 2147483646
-2147483647 <= 2147483647
-1 > -2147483648
-1 > -2147483647
-1 <= -1
-1 <= 0
-1 <= 1
-1 <= 2147483646
-1 <= 2147483647
0 > -2147483648
0 > -2147483647
0 > -1
0 <= 0
0 <= 1
0 <= 2147483646
0 <= 2147483647
1 > -2147483648
1 > -2147483647
1 > -1
1 > 0
1 <= 1
1 <= 2147483646
1 <= 2147483647
2147483646 > -2147483648
2147483646 > -2147483647
2147483646 > -1
2147483646 > 0
2147483646 > 1
2147483646 <= 2147483646
2147483646 <= 2147483647
2147483647 > -2147483648
2147483647 > -2147483647
2147483647 > -1
2147483647 > 0
2147483647 > 1
2147483647 > 2147483646
2147483647 <= 2147483647
于 2012-04-14T09:16:47.313 回答
1

由于您显然可以使用加法，因此在我看来，有一种更简单的方法：

int isGreater(int x, int y) {
    return ((unsigned)(~x + 1 + y)>>31) & 1;
}

基本思想非常简单——从 y 中减去 x，然后检查结果是否为负。为了保持至少一点挑战，我假设我们不能直接做减法，所以我们必须自己否定这个数字（使用二进制补码，所以翻转位并加一个）。

五个操作员——如果包括演员表的话，六个。

值得注意的一点：你的计算same本身就足够了（事实上，你需要消除逻辑否定）。

进行快速测试[编辑：更新测试代码以包含更多边界条件]：

int main() {
    std::cout << isGreater(1, 2) << "\n";
    std::cout << isGreater(1, 1) << "\n";
    std::cout << isGreater(2, 1) << "\n";
    std::cout << isGreater(-10, -11) << "\n";
    std::cout << isGreater(-128, 11) << "\n";
    std::cout << isGreater(INT_MIN, INT_MIN) << "\n";
    std::cout << isGreater(INT_MAX, INT_MAX) << "\n";
    return 0;
}

0
0
1
1
0
0
0
0

...一切如预期。

于 2012-04-14T05:49:38.433 回答