2

特定のビットごとの演算子と他の演算子のみを使用しながら、2 つの 32 ビット整数の合計をオーバーフローなしで計算できるかどうかを判断しようとしています。したがって、整数 x と y をオーバーフローせずに加算できる場合、次のコードは 1 を返し、それ以外の場合は 0 を返します。

(((((x >> 31) + (y >> 31)) & 2) >> 1))

ただし、1 であるべきときに 0 を返し、その逆も同様です。論理 NOT (!) 演算子、またはビットごとの XOR (^) を 0x1 で使用しても、問題は解決しません。

!(((((x >> 31) + (y >> 31)) & 2) >> 1))

(((((x >> 31) + (y >> 31)) & 2) >> 1) ^ 0x1)

^これらは機能しません。

前もって感謝します。

4

5 に答える 5

8

これは少しきれいです：

~(x & y) >> 31

アップデート

クリスのコメントは正しいです。このコードは、2 つの MSB が両方とも設定されていることを確認するだけです。

私はちょうどクリスの答えを見ていましたが、符号なし整数を想定して、単一の加算とビットごとの演算子のみを使用して同じことができることに気づきました。

((x & 0x7FFFFFFF) + (y & 0x7FFFFFFF)) & 0x80000000 & (x | y)

かっこで囲まれた最初のセクションは、両方の MSB を 0 に設定し、結果を追加します。キャリーはすべて、結果の MSB になります。次のビットマスクはそのキャリーを分離します。最後の項は、x または y のいずれかで設定された MSB をチェックします。これにより、キャリー全体が発生します。質問の仕様を満たすには、次のようにします。

~(((x & 0x7FFFFFFF) + (y & 0x7FFFFFFF)) & 0x80000000 & (x | y)) >> 31
于 2010-09-13T00:57:42.770 に答える
2

両方の数値が符号なし整数であると仮定しましょう。符号付き整数を使用する場合、オーバーフローを取得する方法が2つあるため、少し注意が必要です。2つの大きな正の値を追加するか、2つの大きな負の値を追加するかのどちらかです。とにかく、最上位ビットをチェックするだけでは十分ではありません。加算はキャリービットを伝播するため、それを考慮に入れる必要があります。

符号なし整数の場合、簡単な方法をごまかすことを気にしないのであれば、次のようになります。

 (x+y < x) || (x+y < y)

ほとんどのコンパイラはオーバーフローが発生したときに何もしないので、これは機能します。そのままにしておきます。

また、オーバーフローが発生するには、2つの数値の少なくとも1つで最上位ビットを1に設定する必要があることに注意してください。したがって、そのようなものは機能するはずです（注意してください、テストされていません）が、他のバージョンよりもはるかに複雑です。

/* both Most Significant bits are 1 */
(x&y&0x80000000)        
/* x MSb is 1 and carry propagate */
 ||((x&0x80000000)&&(((x&0x7FFFFFFF)+y)&0x80000000))
/* y MSb is 1 and carry propagate */
 ||((y&0x80000000)&&(((y&0x7FFFFFFF)+x)&0x80000000))
于 2010-09-13T02:45:26.520 に答える
1

加算にはキャリーが含まれるため、オーバーフローの単純なビット演算ベースのテストはありません。ただし、オーバーフローの呼び出しや符号なし整数の折り返しを伴わないオーバーフローの簡単なテストがあり、加算してからオーバーフローをチェックするよりもさらに簡単です（もちろん、符号付き整数の未定義の動作です）。

符号なし整数xの場合y：(x<=UINT_MAX-y)

符号付き整数の場合、最初に反対の符号があるかどうかを確認します。もしそうなら、追加は自動的に安全です。両方とも正の場合は、を使用します(x<=INT_MAX-y)。両方とも負の場合は、を使用します(x>=INT_MIN-y)。

于 2010-09-13T04:30:37.687 に答える
1

論理的な！私にとってはうまくいっています。

me@desktop:~$ cat > so.c
#include <stdio.h>

void main() {
    int y = 5;
    int x = 3;
    int t;
    t = (((((x >> 31) + (y >> 31)) & 2) >> 1));
    printf("%d\n", t);
    t = !(((((x >> 31) + (y >> 31)) & 2) >> 1));
    printf("%d\n", t);
}
^D
me@desktop:~$ gcc -o so so.c
me@desktop:~$ ./so
0
1
me@desktop:~$ uname -a
Linux desktop 2.6.32-23-generic #37-Ubuntu SMP Fri Jun 11 07:54:58 UTC 2010 i686 GNU/Linux
于 2010-09-13T01:00:49.540 に答える
0

これらはもしかして符号付き整数ですか？あなたのロジックは、符号なし整数（unsigned int）では問題ないように見えますが、通常の整数では問題ありません。その場合、シフトは符号ビットを保持するためです。

于 2010-09-13T02:07:53.710 に答える