153

このコードは常にfalseと評価されますか？両方の変数は、2の補数の符号付きintです。

~x + ~y == ~(x + y)

条件を満たす数があるはずだと思います。との間の数値をテストしてみましたが、同等には-5000なりませんでした。5000条件の解を見つけるための方程式を設定する方法はありますか？

一方を他方に交換すると、プログラムに潜行性のバグが発生しますか？

4

11 に答える 11

237

矛盾のために、次のようなものがいくつか存在すると仮定しxますy（mod 2 n）

~(x+y) == ~x + ~y

2の補数*により、次のことがわかります。

      -x == ~x + 1
<==>  -1 == ~x + x

この結果に注目すると、次のようになります。

      ~(x+y) == ~x + ~y
<==>  ~(x+y) + (x+y) == ~x + ~y + (x+y)
<==>  ~(x+y) + (x+y) == (~x + x) + (~y + y)
<==>  ~(x+y) + (x+y) == -1 + -1
<==>  ~(x+y) + (x+y) == -2
<==>  -1 == -2

したがって、矛盾。したがって、~(x+y) != ~x + ~yすべてxとy（mod 2 n）に対して。

x* 1の補数演算を使用するマシンでは、実際にはすべてと。に等式が当てはまることに注意してくださいy。これは、1の補数の下で~x = -x。したがって、~x + ~y == -x + -y == -(x+y) == ~(x+y)。

于 2012-06-20T02:35:44.440 に答える
113

2 の補数

大部分のコンピューターでは、 が整数の場合、xは-xとして表され~x + 1ます。同等に、~x == -(x + 1). 方程式でこの代入を行うと、次のようになります。

  • ~x + ~y == ~(x + y)
  • -(x+1) + -(y+1) = -((x + y) + 1)
  • -x - y - 2 = -x - y - 1
  • -2 = -1

これは矛盾しているため、~x + ~y == ~(x + y)常にfalseです。

そうは言っても、衒学者は、C は 2 の補数を必要としないので、考慮しなければならないことを指摘するでしょう...

1の補数

の補数では、-xは単に として表され~xます。ゼロは特殊なケースで、すべて 0 の ( +0) とすべて 1 の ( -0) 表現の両方がありますが、IIRC、C では+0 == -0ビット パターンが異なっていても必要なので、これは問題になりません。~に置き換えるだけ-です。

  • ~x + ~y == ~(x + y)
  • -x + (-y) = -(x + y)

これはすべてのとに当てはまります。xy

于 2012-06-20T05:42:05.910 に答える
32

x両方の右端のビットのみを考えyます (つまり、x == 13どちらが1101基数 2 の場合は、最後のビット a のみを調べます1)。次に、4 つのケースが考えられます。

x = 0、y = 0:

左側: ~0 + ~0 => 1 + 1 => 10
右側: ~(0 + 0) => ~0 => 1

x = 0、y = 1:

左側: ~0 + ~1 => 1 + 0 => 1
右側: ~(0 + 1) => ~1 => 0

x = 1、y = 0:

これは宿題なのでお任せします (ヒント: x と y を入れ替えたものは前と同じです)。

x = 1、y = 1:

こちらもお任せします。

可能な入力が与えられた場合、式の左辺と右辺で右端のビットが常に異なることを示すことができます。したがって、少なくとも 1 つのビットが反転しているため、両方の辺が等しくないことが証明されました。互いに。

于 2012-06-20T02:25:19.980 に答える
27

ビット数がnの場合

~x = (2^n - 1) - x
~y = (2^n - 1) - y


~x + ~y = (2^n - 1) +(2^n - 1) - x - y =>  (2^n + (2^n - 1) - x - y ) - 1 => modulo: (2^n - 1) - x - y - 1.

今、

 ~(x + y) = (2^n - 1) - (x + y) = (2^n - 1) - x - y.

したがって、それらは常に等しくなく、差は 1 です。

于 2012-06-20T02:21:15.067 に答える
27

ヒント：

x + ~x = -1(mod 2 n )

質問の目的が (C 仕様を読むスキルではなく) 数学をテストすることであると仮定すると、これで答えが得られるはずです。

于 2012-06-20T02:24:52.570 に答える
10

1 の補数でも 2 の補数でも (さらには 42 の補数でも)、これは次のように証明できます。

~x + ~y == ~(x + a) + ~(y - a)

それでは、次のようa = yにします。

~x + ~y == ~(x + y) + ~(y - y)

また：

~x + ~y == ~(x + y) + ~0

したがって、2 の補数 that~0 = -1では、命題は偽です。

の補数で~0 = 0は、命題は真です。

于 2012-06-20T13:12:40.833 に答える
7

Dennis Ritchie の著書によると、C はデフォルトで 2 の補数を実装していません。したがって、あなたの質問が常に正しいとは限りません。

于 2012-06-20T04:12:24.807 に答える
5

で表さMAX_INTれる int とします011111...111(ただし、ビット数が多い場合)。次に、 と を知っているので、~x + x = MAX_INTと~y + y = MAX_INTの差が であることを確実に知ることが~x + ~yでき~(x + y)ます1。

于 2012-06-20T03:21:16.947 に答える
5

C では、2 の補数を実装する必要はありません。ただし、符号なし整数の場合、同様のロジックが適用されます。このロジックでは、差は常に 1 になります。

于 2012-06-20T03:23:59.897 に答える
3

もちろん、C では 2 の補数表現が必要ないため、この動作は必要ありません。たとえば、~x = (2^n - 1) - x&~y = (2^n - 1) - yはこの結果を取得します。

于 2012-06-21T14:21:25.430 に答える
0

ああ、基本的な離散数学!

ド・モルガンの法則を調べる

~x & ~y == ~(x | y)

~x | ~y == ~(x & y)

ブール証明にとって非常に重要です!

于 2012-06-23T01:25:33.450 に答える