CODEWITHSUNDEEP
algorithmbit-manipulationxor
Anil Kumar K K
Anil Kumar K K

Reputation: 1435

Bitwise XORing two numbers results in sum or difference of the numbers

When I XOR any two numbers, I am getting either absolute value of their difference or sum. I have searched a lot on Google trying to find out any relevant formula for this. But no apparent formula or statement is available on this.

Example:

10 XOR 2 = 1010 XOR 10 = 1000(8)
 1 XOR 2 =   01 XOR 10 =   11(3)

Is it true for all the numbers?

Upvotes: 8

Views: 10276

Answers (4)

user555045
user555045

Reputation: 64904

As shown by Dukelings answer and CmdrMoozy's comment, it's not always true. As shown by your post, it's true at least sometimes. So here's a slightly more detailed analysis.

The +-side

Obviously, if (but not only if) (x & y) == 0 then (x ^ y) == x + y, because
x + y = (x ^ y) + ((x & y) << 1)

That accounts for 332 cases (for every bit position, there are 3 choices that result in a 0 after the AND) where (x ^ y) == (x + y).

Then there are the cases where (x & y) != 0. Those cases are precisely the cases such that
(x & y) == 0x80000000, because the carry out of the highest bit is the only carry that doesn't affect anything.

That adds 331 cases (for 31 bit positions there are 3 choices, for the highest bit there is only 1 choice).

The --side

For subtraction, there's the lesser known identity x - y == (x ^ y) - ((~x & y) << 1).

That's really not too different from addition, and the analysis almost the same. This time, if (but not only if) (~x & y) == 0 then (x ^ y) == x - y. That ~ doesn't change the number of cases: still 332. Most of them are different cases than before, but not all (consider y = 0, then x can be anything).

There are again 331 extra cases, this time from (~x & y) == 0x80000000.

Both sides

The + and - sides aren't disjoint. Sometimes, x ^ y = x + y = x - y. That can only happen when either y = 0 or y = 0x80000000. If y = 0, x can be anything because (x & 0) == 0 and (~x & 0) == 0 for all x. If y = 0x80000000, x can again be anything, this time because x & 0x80000000 and ~x & 0x80000000 can both either work out to 0 or to 0x80000000, and both are fine.

That gives 233 cases where x ^ y = x + y = x - y.

It also gives (332 + 331) * 2 - 233 cases where x ^ y is x + y or x - y or both, which is 4941378580336984 or in base 16, 118e285afb5158, which is also the answer given by this site.

That's a lot of cases, but only roughly 0.02679% of the total space of 264.

Upvotes: 7

7575 mohan
7575 mohan

Reputation: 21

Let assume N is power of 2 for some K (N=2 pow k) then

0<=X<N --> N XOR X is always sum of N and X

N<=Y<(2 pow k+1) --> N XOR Y is always diff of N and Y

Upvotes: 0

Shaswat Lenka
Shaswat Lenka

Reputation: 604

Actually, there's an interesting answer to your observation and it can be explained why you observe this for so many numbers.
There's a relationship between a + b and a ^ b. It is given by:

a + b = a^b + 2*(a & b)

Hence,

a^b = a + b - 2*(a & b)

(where ^ is the bitwise XOR and & is bitwise AND)
see this link to get some more idea about the above relation. Hence, for every a and b, where a & b = 0 you will get a+b = a^b which explains the sum part. And if a & b is not equal to 0, then that explains the difference part. Hope it clarifies your question! :D

Upvotes: 2

Bernhard Barker
Bernhard Barker

Reputation: 55589

No, it's not always true.

6 = 110
3 =  11
   ----
XOR 101 = 5

SUM   9
DIFF  3

This is by no means a complete analysis, but here's what I see:

For your first example, the least significant bits of 1010 are the same as the bits of 10, which would cause that you get the difference when XORing.

For your second example, all the corresponding bits are different, which would cause that you get the sum when XORing.

Why these properties hold should be fairly easy to see.

Upvotes: 4

Related Questions