XOR of Two Numbers

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:

Confused about your next job?

In 4 simple steps you can find your personalised career roadmap in Software development for FREE



Expand in New Tab 

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)
Previous Post
Edit Distance Problem

Edit Distance Problem

Next Post
Graph Coloring Problem

Graph Coloring Problem

Total
0
Share