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

Steve picture Steve · Jun 20, 2012 · Viewed 8.4k times · Source

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

Alex Lockwood picture Alex Lockwood · Jun 20, 2012

Assume for the sake of contradiction that there exists some x and some y (mod 2n) 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 2n).


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