# XOR of Two Numbers

## Problem Statement

Given 2 numbers, find their bitwise XOR, without using the bitwise XOR operator.

Sample Test Cases

Input 1: x = 3, y = 5
Output 1: 6
Explanation 1:

x = 011
y = 101
R = 110 = 6 (Taking the bitwise XOR)

Input 2: x = 1, y = 2
Output 2: 3
Explanation 2:

x = 001
y = 010
R = 011 = 3 (Taking the bitwise XOR)

## Approach 1 (Naive Approach)

In the naive approach, we can just simulate what the XOR operation does, i.e,

• If the bits at the ith position are the same we put 0 at that position.
• Else if the bits at the ith position are different we put 1 at that position.

We can easily do this by traversing over all the bits of the result and setting each bit of the result as told above. The implementation is done considering the numbers as 32-bit integers.

### C++ Implementation

```int getXOR(int x, int y) {
int ans = 0;
for (int i = 0; i <= 31; i++) {
if (((1 LL << i) & x) != ((1 LL << i) & y)) {
ans |= (1 LL << i);
}
}
return ans;
}```

### Java Implementation

```public static int getXOR(int x, int y) {
int res = 0;
for (int i = 0; i <= 31; i++) {
if (((1 << i) & x) != ((1 << i) & y)) {
res |= (1 << i);
}
}
return res;
}```

### Python Implementation

```def getXOR(x, y):
res = 0
for i in range(32):
if ((1 << i) & x) != ((1 << i) & y):
res |= 1 << i
return res```

### Complexity Analysis

• Time Complexity: O(log2(n))
• Space Complexity: O(1)

## Approach 2 (Using other bitwise operators):

We can optimize the above solution by simulating the XOR operation without using the for loop as follows:

• We find all the bits where either x’s or y’s bits are set (Bitwise OR of the numbers).
• We need to remove those set bits where both x and y are set ( ~x OR ~y).
• Bitwise AND of the above expressions gives the desired result.

### C++ Code

```int getXOR(int x, int y) {
return (x | y) & (~x | ~y);
}```

### Java Code

```public static int getXOR(int x, int y) {
return (x | y) & (~x | ~y);
}```

### Python Code

```def getXOR(x, y):
return (x | y) & (~x | ~y)```

### Complexity Analysis

• Time Complexity: O(1)
• Space Complexity: O(1)

## Approach 3(Using the XOR-AND-SUM Property)

We can calculate the XOR of 2 numbers using the well-known property of XOR,

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

### C++ Code – Using XOR & SUM

```int getXOR(int x, int y) {
return (x + y) - 2 * (x & y);
}```

### Java Code – Using XOR & SUM

```public static int getXOR(int x, int y) {
return (x + y) - 2 * (x & y);
}```

### Python Code – Using XOR & SUM

```def getXOR(x, y):
return (x + y) - 2 * (x & y)```

### Complexity Analysis

• Time Complexity: O(1)
• Space Complexity: O(1)