Why does negating a value change the result when XORing it with 1?

Question

I know the working of XOR,

Console.WriteLine(1^1);  // returns 0

results to

00000001
00000001 
--------
00000000

but how does this return 2?

Console.WriteLine(-(-1^1)); // returns 2

An interesting coincidence to see this question in the "Hot Questions" list. I just used this same trick in [an answer on Code Golf](https://codegolf.stackexchange.com/questions/118819/swap-the-parity/119057#119057). — Cody Gray - on strike, May 05 '17 at 10:16
I cast a binding vote to close this question as a duplicate, but that automatically deleted Jason C's comment that had originally persuaded me to do so. I'll quote the relevant portion: *"More than enough info there to answer all specific cases (it doesn't really make sense to leave questions floating around about explaining the results of every possible arbitrary combination of integers and operations without linking them back to a post with enough fundamentals to deduce every answer; now that an explanatory answer's been added here it's time to set up the sign post…)"* — Cody Gray - on strike, May 05 '17 at 16:27

score 31 · Accepted Answer · edited May 23 '17 at 12:02

31

-1 is stored as a value with all bits set to 1. If we are staying on your 8 bits example, -1 would then be equal to 11111111. So -1^1 gives the following:

11111111
00000001 
--------
11111110

Which is equal to -2. When you invert it with another minus, you get 2.

Negative numbers are stored in a way we call two's complement of the number. If you want to compute it quickly in your head, you can just flip all the bits of the positive equivalent of your number, and add one to it. So for -1:

 1: 00000001
    --------
    11111110
   +       1
    --------
-1: 11111111

Explaining why -1 is stored as 11111111.

If you want to understand two's complement a bit more, this question may also help you.

edited May 23 '17 at 12:02

Community

1
1

answered May 05 '17 at 07:46

Izuka

2,572
5
29
34

This is basically correct, but you aren't showing nearly enough bits here for an `int`. Rather than saying, *"-1 is stored as 11111111"*, it would be simpler and more correct to say that -1 is stored as a value with *all bits set*. – Cody Gray - on strike May 05 '17 at 10:14
1

@CodyGray I edited my answer to reflect this fact. – Izuka May 05 '17 at 10:33
Is twos compliment actually required by C#? Or just happens to be the OPs implementation? – Vality May 05 '17 at 14:35
1

@Vality [Yes](http://stackoverflow.com/questions/26225119/is-c-net-signed-integer-overflow-behavior-defined/26225204#comment62400548_26225204), if you follow the C# 5.0 and ECMA-335 6th ed. (CLI) specs. – Bob May 05 '17 at 15:39
1

The ECMA C# standard (but oddly not the Microsoft C# spec) requires that `System.Int32` meets the requirements of the CLI spec, even if not running on a CLI implementation. The CLI spec requires that `System.Int32` is equivalent to its `int32` data type which is required to be twos compliment (similar requirements for other types). Thus all standards compliant c# implementations must be twos complement. Further both the C# standard and spec defines the range and size of integers to be identical to twos complement, and the shift operators as specified assume twos complement in their design. – Kevin Cathcart May 05 '17 at 15:55

Michał · Answer 2 · 2017-11-10T22:42:34.610

This expression is interpreted by the compiler as:

-((-1)^1)

which is: - ((11111111) XOR (00000001)) = -(11111110) = - (-2) = 2

To understand why the compiler chooses -((-1)^1) instead of -(-(1^1)), take a look at this article about C# operators precedence. The most relevant piece is that the unary - operator (the bolded one: -( - 1^1) ) has a higer precedence than the XOR operator ^. Therefore the negation happens before XOR, and we end up with -((-1)^1).

I am using 8 bits per integer here. Normally you should expect 32 or 64 bits per number, but in this case it is irrelevant;

To better understand why 11111111 is -1, and 11111110 is -2, read more about two's complement - https://en.wikipedia.org/wiki/Two%27s_complement. In short, you treat all the bits apart from the left-most, as consecutive powers of 2. The leftmost bit is treated as the next-power, but negative.

Example:

10001100 = 1 * (-(2^7)) + 0 * 2^6 + 0 * 2^5 + 0 * 2^4 + 1*2^3 + 1*2^2 + 1*2^1 + 1*2^0

Dmitry Bychenko · Answer 3 · 2017-05-05T07:56:03.607

5

Negative numbers are represented as a binary complement, i.e.

-x == ~x + 1

So we have

 -(-1 ^ 1) ==
 -(0b11111...1111 ^ 1) ==
 -(0b11111...1110) ==
  2

edited May 05 '17 at 07:56

answered May 05 '17 at 07:50

Dmitry Bychenko

180,369
20
160
215

score 4 · Answer 4 · edited May 23 '17 at 12:26

4

I'm assuming signed Int32s.

   -1   11111111111111111111111111111111 (two's complement)
    1   00000000000000000000000000000001
-----------------------------------------
  -1^1  11111111111111111111111111111110
-(-1^1) 00000000000000000000000000000010 --> 2

See C# operator precedence and two's complement.

edited May 23 '17 at 12:26

Community

1
1

answered May 05 '17 at 07:52

themiurge

1,619
17
21

It has nothing to do with how many bits there are in an int, only with two's complement. – Mr Lister May 05 '17 at 12:23
Who said it does? – themiurge May 05 '17 at 12:50
You said you were assuming Int32s, implying that it might not be the same for other word sizes. – Mr Lister May 05 '17 at 13:26
I'm sorry, I didn't imply that at all. I chose 32-bit integers just because that's how C# would store literals. I meant "assuming" as in "for the sake of the argument". – themiurge May 05 '17 at 13:38

score 3 · Answer 5 · answered May 05 '17 at 07:47

3

In binary using two's complement; 11111111^00000001=11111110. Binary two's complement 11111110 is decimal -2.

answered May 05 '17 at 07:47

Taemyr

3,407
16
26

Matt · Answer 6 · 2017-05-05T08:07:42.027

-1 is 11111111 (check two's complement for that) when you make a xor with 1 which is 00000001 you have : 11111110 which is -2 (again two's complement)

To well understand two's complement (mathematics can be quite abstract), here is what I keep in mind :

0 = 00...00

1 = 00...001

...

max - 1 = 011...110

max = 011...11

min = 100...00

min + 1 = 100...001

...

-1 = 11...11

Obviously, min and max depend on the number of bits you use to represent your integers

score 2 · Answer 7 · answered May 05 '17 at 07:51

2

int has 32 bits.

-1 is equals to 1111 1111 1111 1111 1111 1111 1111 1111

1 is equals to 0000 0000 0000 0000 0000 0000 0000 0001

so -1 ^ 1 equals to 1111 1111 1111 1111 1111 1111 1111 1110 which is equals to -2

so (-(-1^1)) = 2

look at bit representations for integers and floating points numbers for more information.

answered May 05 '17 at 07:51

Renuka

136
6

It has nothing to do with how many bits there are in an int, only with how they are _stored_ (two's complement). – Mr Lister May 05 '17 at 12:24

Why does negating a value change the result when XORing it with 1?

7 Answers7