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

Question

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).}

Two's Complement

On the vast majority of computers, if x is an integer, then -x is represented as ~x + 1. Equivalently, ~x == -(x + 1). Making this substution in your equation gives:

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

which is a contradiction, so ~x + ~y == ~(x + y) is always false.

---

That said, the pedants will point out that C doesn't require two's complement, so we must also consider...

One's Complement

In one's complement, -x is simply represented as ~x. Zero is a special case, having both all-0's (+0) and all-1's (-0) representations, but IIRC, C requires +0 == -0 even if they have different bit patterns, so this shouldn't be a problem. Just substitute ~ with -.

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

which is true for all x and y.

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.

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.

In both one's and two's (and even in 42's) complement, this can be proved:

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

Now let a = y and we have:

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

or:

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

Therefore in two's complement that ~0 = -1, the proposition is false.

In one's complement that ~0 = 0, the proposition is true.