Write a program to find XOR of two numbers without using XOR operator.

Naive Solution would be to consider every bit present in both numbers one by one (either from left or right) and compare them. If the current bit is same in both numbers (i.e. both are 0 or both are 1), we set it as 0 else we set it as 1 and move to next pair of bits until all bits are processed.

The expression ((x | y) – (x & y)) is equivalent to x ^ y (finding XOR of two numbers x and y). XOR works by setting the bits which are set in either of one of the given numbers (0 ^ 1 = 1,

1 ^ 0 = 1) and finally taking out the common bits present in both numbers (1 ^ 1 = 0).

For example,

01000001 | (x = 65)

01010000 (y = 80)

~~~~~~~~

01010001 (x | y)

01000001 & (x = 65)

01010000 (y = 80)

~~~~~~~~

01000000 (x & y)

Now the result x ^ y would be (x | y) – (x & y) = (01010001 – 01000000) = 00010001

## C++

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
#include <iostream> #include <bitset> using namespace std; // Function to find XOR of two numbers without using XOR operator int findBits(int x, int y) { return (x | y) - (x & y); } // Find XOR of two numbers without using XOR operator int main() { int x = 65; int y = 80; cout << "First number in binary is " << bitset<8>(x) << endl; cout << "Second number in binary is " << bitset<8>(y) << endl; cout << "\nXOR is " << bitset<8>(findBits(x, y)); return 0; } |

**Output: **

First number in binary is 01000001

Second number in binary is 01010000

XOR is 00010001

**Read More –**

Bit Hacks – Part 1 (Basic)

Bit Hacks – Part 2 (Playing with k’th bit)

Bit Hacks – Part 3 (Playing with rightmost set bit of a number)

Bit Hacks – Part 4 (Playing with letters of English alphabet)

Bit Hacks – Part 5 (Find absolute value of an integer without branching)

**Suggested Read: **https://graphics.stanford.edu/~seander/bithacks.html

**Thanks for reading.**

Please use ideone or C++ Shell or any other online compiler link to post code in comments.

Like us? Please spread the word and help us grow. Happy coding 🙂

## Leave a Reply

Hey,

I am unable to understand how x^y = ((x | y) – (x & y)).

I did a quick search on wikipedia and it says x^y = x.y’ + x’.y = (x+y).(x’+y’) where x’ represents complement of x.

Can you please explain?

Hello,

(x | y) sets the bits which are set in either x or y i.e. (0 | 1 = 1, 1 | 0 = 1 or 1 | 1 = 1)

(x & y) sets only the common bits present in both x and y (1 | 1 = 1).

So if we subtract both numbers, the result will have 0 wherever both x and y are set and 1 where either x or y is set, which is exactly what XOR does. Please refer the given example if you’re still unclear.

Thanks. I got the proof that you gave in the description.

I was just wondering if x ^ y = (X | y) – (x & y) is a universal formula?