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

Question

Does this code always evaluate to false? Both variables are two's complement signed ints.

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

I feel like there should be some number that satisfies the conditions. I tried testing the numbers between -5000 and 5000 but never achieved equality. Is there a way to set up an equation to find the solutions to the condition?

Will swapping one for the other cause an insidious bug in my program?

Answer 1

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

Answer 2

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.

Answer 3

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.

Answer 4

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.

Answer 5

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.

Answer 6

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.

Answer 7

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

Answer 8

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.

Answer 9

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!

Answer 10

Of course, C doesn't require this behavior because it no require two's complement representation. For example, ~x = (2^n - 1) - x & ~y = (2^n - 1) - y will get this result.

Answer 11

Ah, fundamental discrete mathematics!

Check out De Morgan's Law

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

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

Very important for Boolean proofs!