小开

If the number of bits is 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.

Now,

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

Hence, they'll always be unequal, with a difference of 1.

小开

Hint:

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

Assuming the goal of the question is testing your math (rather than your read-the-C-specifications skills), this should get you to the answer.

小开

Consider only the rightmost bit of both x and y (IE. if x == 13 which is 1101 in base 2, we will only look at the last bit, a 1) Then there are four possible cases:

x = 0, y = 0:

LHS: ~0 + ~0 => 1 + 1 => 10
RHS: ~(0 + 0) => ~0 => 1

x = 0, y = 1:

LHS: ~0 + ~1 => 1 + 0 => 1
RHS: ~(0 + 1) => ~1 => 0

x = 1, y = 0:

I will leave this up to you since this is homework (hint: it is the same as the previous with x and y swapped).

x = 1, y = 1:

I will leave this one up to you as well.

You can show that the rightmost bit will always be different on the Left Hand Side and Right Hand Side of the equation given any possible input, so you have proven that both sides are not equal, since they have at least that one bit that is flipped from each other.

小开

最佳答案

Assume for the sake of contradiction that there exists some x and some y (mod 2ⁿ) such that

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

By two's complement*, we know that,

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

Noting this result, we have,

      ~(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

Hence, a contradiction. Therefore, ~(x+y) != ~x + ~y for all x and y (mod 2ⁿ).

^{*It is interesting to note that on a machine with one's complement arithmetic, the equality actually holds true for all x and y. This is because under one's complement, ~x = -x. Thus, ~x + ~y == -x + -y == -(x+y) == ~(x+y).}

小开

Letting MAX_INT be the int represented by 011111...111 (for however many bits there are). Then you know that, ~x + x = MAX_INT and ~y + y = MAX_INT, so therefore you will know for certain that the difference between ~x + ~y and ~(x + y) is 1.

小开

C does not require that two's complement be what is implemented. However, for unsigned integer similar logics is applied. Differences will always be 1 under this logic!

小开

According to the book by Dennis Ritchie, C does not implement two's complement by default. Therefore, your question might not always be true.

小开

二的补语

在大多数很大计算机上，如果 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)总是假的。

也就是说，学究们会指出 C 不需要两个补语，所以我们也必须考虑..。

补语

在互相补充中，-x简单地表示为 ~x。Zero 是一个特例，它同时具有 all-0(+0)和 all-1(-0)表示，但是 IIRC，C 需要 +0 == -0，即使它们具有不同的位模式，所以这应该不成问题。用 -代替 ~。

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

对于所有的 x和 y都是没错。

小开

在1和2的(甚至在42的)补语中，这可以被证明:

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

现在让 a = y，我们有:

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

或:

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

因此在两个补语中，~0 = -1的命题是错误的。

在 ~0 = 0的补语中，这个命题是正确的。

小开

当然，C 不需要这种行为，因为它不需要二进制的补数表示。例如，~x = (2^n - 1) - x和 ~y = (2^n - 1) - y将得到这个结果。

小开

啊，基本离散数学！

看看德摩根定律

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


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

非常重要的布尔证明！

~x + ~y == ~(x + y) is always false?

二的补语

补语