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

Be aware that in the cases of signed integer overflow, it is technically undefined behavior. So it's possible for it to return `true` even if they can never be assuming strict two's complement. — Mysticial, Jun 20 '12 at 02:18
@Steve: You could demonstrate that you've tried all the usual suspects (-1, 0, 1, 2, and so on) in all combinations, as well as your attempts to "solve" the problem for small word-sizes (three bits? four bits?). That'd definitely help convince us that we're not just helping someone get something they did not try to earn for themselves first. :) — sarnold, Jun 20 '12 at 02:22
@AlexLockwood When I first posted the question, I assumed tagging the question as "homework" asks people to provide clues to help me solve the problem (as the description of the "homework" tag states) and not just give answers. That's why I just plainly asked the problem's question :) — Steve, Jun 20 '12 at 03:21
@zeacuss, De Morgan's law would apply if the question asked `!x | !y == !(x & y)` — Alex Lockwood, Jun 25 '12 at 16:32
@AlexLockwood ur expression evaluates to true, where the expression in the question evaluates to false... `~x + ~y == ~(x + y)` is the same as `~(x . y) == ~(x + y)` which evaluates to false... please note that in boolean logic `. is the same as &` and `+ is the same as |` and when you put boolean operators in an expression it is evaluated as boolean not numbers — zeacuss, Jun 26 '12 at 14:57
@zeacuss, yes but `~` is not the same as `!`, so saying `~x + ~y == ~(x . y)` is incorrect. De Morgan's laws involve boolean negation, not bitwise negation. — Alex Lockwood, Jun 26 '12 at 15:03
I'm not familiar with this information, nor do I currently have a C compiler to check it...so, ok — zeacuss, Jun 26 '12 at 15:14
@AlexLockwood I think DeMorgan doesn't apply not because of a difference between boolean and bitwise negation, but because of the difference between addition and disjunction (and between multiplication and conjunction). — jcsahnwaldt Reinstate Monica, Jun 26 '12 at 18:53
@JonaChristopherSahnwaldt, yes, that is a better reason, thanks :) — Alex Lockwood, Jun 26 '12 at 19:24
As I've read this question and some of the answers, I'm wondering what the point of the question is? Based on some of the answers, it would appear to be a case of pure mental masterbation. Kind of makes me wonder why the stack overflow moderators let this question live. I've seem far to many questions *closed* because they violated some cardinal rule of "why stackoverflow exists", and yet this question - for which I've yet to see anything that explains "What's the point?" other than an theoretical exercise -- continues to live on — Zeke Hansell, Jun 26 '12 at 19:29

Alex Lockwood · Accepted Answer · 2012-06-20T13:47:10.207

236

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

edited Jun 20 '12 at 13:47

answered Jun 20 '12 at 02:35

Alex Lockwood

83,063
39
206
250

47

Of course, C doesn't require this behavior; as it doesn't require two's complement representation. – Billy ONeal Jun 20 '12 at 02:43
12

Btw, the equality is **true** for one's complement. NOT operation is not really defined for number in general, so mixing NOT with addition results in different behavior depending on the representation of the number. – nhahtdh Jun 20 '12 at 02:50
9

One could just restate the problem to be for *unsigned integers* and then twos complement does not come into play at all. – R.. GitHub STOP HELPING ICE Jun 20 '12 at 03:20
3

For unsigned integer it is true as -1 == 2^n-1 in Z_{2^n}. – Maciej Piechotka Jun 20 '12 at 08:13
5

Even simpler, IMHO: `~x == -(x+1)`, so `~(x+y) == ~x + ~y` implies `-(x+y+1) == -(x+1) + -(y+1)` implies `-1 == -2` – BlueRaja - Danny Pflughoeft Jun 20 '12 at 16:25
5

@AlexLockwood: I'm not trying to be "that guy." I'm not saying that saying two's complement is bad; just that saying "this works on two's complement machines" or something to that effect in the answer is fine. (Which you did, which is why I didn't downvote you :) ) I just wanted to point out that C does allow for alternate representations of signed numbers. – Billy ONeal Jun 20 '12 at 17:54
7

@BillyONeal, don't worry, I was only joking and I appreciate that you mentioned it :). I'll buy you a drink on the day that I encounter a machine that performs one's complement arithmetic... how does that sound? haha – Alex Lockwood Jun 20 '12 at 18:58
Where did the last line come from? `~(x+y) + (x+y) == -1` – Cameron Martin Jun 20 '12 at 21:31
Let `a = x+y`. Then `~(x+y) + (x+y) == ~a + a == -1` by two's complement arithmetic. – Alex Lockwood Jun 20 '12 at 21:39
None of the operations do anything different for unsigned numbers. ~, +, - all do exactly the same bit operations on signed vs unsigned numbers. – phkahler Jun 21 '12 at 18:50

score 113 · Answer 2 · edited Jun 22 '12 at 19:13

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.

+1 for an answer that actually considers both two's complement and one's complement on equal ground. — user, Jun 20 '12 at 07:12
@dan04, `+0 == -0`. Finally something that makes sense in C. :) — Alex Lockwood, Jun 20 '12 at 13:25

Paul · Answer 3 · 2015-01-19T17:26:23.803

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.

Karthik Kumar Viswanathan · Answer 4 · 2012-06-20T02:33:02.313

27

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.

edited Jun 20 '12 at 02:33

answered Jun 20 '12 at 02:21

Karthik Kumar Viswanathan

1,786
11
13

4

@nhahtdh and how do you define `~` operation on non-fixed width numbers? – hamstergene Jun 20 '12 at 02:27
1

I gave this answer with these number of bits so that it's easy to correlate with what's taught in classes. Note that ~x is highly dependent on the number of bits, n, used to represent the number. So it's sensible to stick to one, when trying to verify this experimentally. – Karthik Kumar Viswanathan Jun 20 '12 at 02:27
1

@hamstergene: I know that the number of bits is fixed, but my point is that it doesn't have to be those amount (8, 16, etc.). – nhahtdh Jun 20 '12 at 02:29
@nhahtdh but he's just proved it for *any* amount – hamstergene Jun 20 '12 at 02:30
1

Those are values for which it's easy to write a program to verify the answer. It works for any n, as long as ~x and ~y are written to match that given . – Karthik Kumar Viswanathan Jun 20 '12 at 02:30
1

@hamstergene: I don't have problem with the proof, just that the numbers gives the false implication that it only works for those cases. – nhahtdh Jun 20 '12 at 02:32
No, it doesn't. I'm going to remove that parenthesis, if it makes you any happier. – Karthik Kumar Viswanathan Jun 20 '12 at 02:32
@KarthikKumarViswanathan: Nope, I don't have problem with your answer. The main point is good enough. – nhahtdh Jun 20 '12 at 02:33

score 27 · Answer 5 · edited Jun 22 '12 at 00:27

27

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.

edited Jun 22 '12 at 00:27

Alex Lockwood

83,063
39
206
250

answered Jun 20 '12 at 02:24

user541686

205,094
128
528
886

2

Only on two's complement machines. (The C standard doesn't require that) – Billy ONeal Jun 20 '12 at 02:42
12

@Billy: That's like saying "only for two-armed people". – dan04 Jun 20 '12 at 05:03
2

@dan04: No, it isn't. I would love to say all the signed magnitude and ones complement representations were gone from the world. But I would be wrong in saying that. The C standard doesn't allow you to make that assumption; therefore I would say code that makes that assumption is bad code most of the time. (Particularly when there are usually better ways of messing with signed numbers than bit twiddling; and particularly when unsigned numbers are probably a better choice most of the time anyway) – Billy ONeal Jun 20 '12 at 17:53

score 10 · Answer 6 · answered Jun 20 '12 at 13:12

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.

score 7 · Answer 7 · answered Jun 20 '12 at 04:12

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.

answered Jun 20 '12 at 04:12

user1457474

113
4

Adrian Monk · Answer 8 · 2012-06-24T04:15:12.290

5

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.

edited Jun 24 '12 at 04:15

answered Jun 20 '12 at 03:21

Adrian Monk

1,061
9
17

user1422551 · Answer 9 · 2012-06-25T16:30:58.803

5

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!

edited Jun 25 '12 at 16:30

answered Jun 20 '12 at 03:23

user1422551

73
6

score 3 · Answer 10 · edited Jun 23 '12 at 17:10

3

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.

edited Jun 23 '12 at 17:10

Alex Lockwood

83,063
39
206
250

answered Jun 21 '12 at 14:21

user1472392

31
4

score 0 · Answer 11 · edited Jul 06 '12 at 05:15

0

Ah, fundamental discrete mathematics!

Check out De Morgan's Law

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

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

Very important for Boolean proofs!

edited Jul 06 '12 at 05:15

Alex Lockwood

83,063
39
206
250

answered Jun 23 '12 at 01:25

David Kaczynski

1,246
2
20
36

Just plain wrong. In C + is addition, * multiplication and not boolean or or and. – nalply Jun 26 '12 at 19:37
Thank you for pointing out the incorrect operators, nalply. It has now been updated with the correct operators, although you are correct in that it does not apply to the original question. – David Kaczynski Jun 27 '12 at 17:47
1

Well, if true is one and false is zero, then + and * behave exactly as or and and, moreover two's complement behaves like not, hence the law applies nonetheless. – a1an Jun 27 '12 at 21:56
Thank you for pointing that out, a1an. I was trying to think of how De Morgan's Laws could still be applicable to the original question, but it has been several years since I studied either C programming or Discrete Mathematics. – David Kaczynski Jun 28 '12 at 16:04

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

11 Answers11

Two's Complement

One's Complement