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(log₂(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)