2

最大 24 個の演算子を使用してビット単位のメソッドを作成する必要がある宿題をしています。私のコードは機能します...しかし、25 の演算子があり、1 つ多すぎます。コードを実行するためのより効率的な方法を見つけられる人はいますか?

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

これでオペレーターが 1 人減ります。

于 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

sが32ビット幅であると仮定するとint、これを置き換えることができます。

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

これとともに：

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

そして、もう1つ自分を救ってください。

于 2012-04-14T05:02:51.543 に答える
2

この行：

return 0 | (~equal & check2);

次のように簡略化できます。

return (~equal & check2);

(ビットごとのorwith0は何の効果もありません)

于 2012-04-14T04:54:01.143 に答える
1

INT_MINからまでの int の範囲全体を処理する、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 を減算し、結果が負かどうかを確認します。少なくとも少し挑戦し続けるために、減算を直接行うことはできないと想定しているため、自分で数値を否定する必要があります (2 の補数を使用するため、ビットを反転して 1 を追加します)。

5 つのオペレーター (キャストを含めると 6 つ)。

注目すべき点: の計算は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 に答える