Data Modelling & AI Data Structure & Algorithm

Find XOR of two number without using XOR operator

31 July 2024

0

Given two integers, find XOR of them without using the XOR operator, i.e., without using ^ in C/C++.

Examples :

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

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

A Simple Solution is to traverse all bits one by one. For every pair of bits, check if both are the same, set the corresponding bit like 0 in output, otherwise set it as 1.

C++

// C++ program to find XOR without using ^
#include <iostream>
using namespace std;
 
// Returns XOR of x and y
int myXOR(int x, int y)
{
    int res = 0; // Initialize result
     
    // Assuming 32-bit Integer 
    for (int i = 31; i >= 0; i--)                     
    {
       // Find current bits in x and y
       bool b1 = x & (1 << i);
       bool b2 = y & (1 << i);
        
        // If both are 1 then 0 else xor is same as OR
        bool xoredBit = (b1 & b2) ? 0 : (b1 | b2);          
 
        // Update result
        res <<= 1;
        res |= xoredBit;
    }
    return res;
}
 
// Driver program to test above function
int main()
{
   int x = 3, y = 5;
   cout << "XOR is " << myXOR(x, y);
   return 0; 
}

C

// C program to find XOR without using ^
#include <stdio.h>
#include <stdbool.h> //to use bool
 
// Returns XOR of x and y
int myXOR(int x, int y)
{
    int res = 0; // Initialize result
 
    // Assuming 32-bit Integer
    for (int i = 31; i >= 0; i--)
    {
       
        // Find current bits in x and y
        bool b1 = x & (1 << i);
        bool b2 = y & (1 << i);
 
        // If both are 1 then 0 else xor is same as OR
        bool xoredBit = (b1 & b2) ? 0 : (b1 | b2);
 
        // Update result
        res <<= 1;
        res |= xoredBit;
    }
    return res;
}
 
// Driver Code
int main()
{
    int x = 3, y = 5;
    printf("XOR is %d\n", myXOR(x, y));
    return 0;
}
 
// This code is contributed by phalashi.

Java

// Java program to find XOR without using ^
import java.io.*;
 
class GFG{
   
// Returns XOR of x and y
static int myXOR(int x, int y)
{
     
    // Initialize result
    int res = 0; 
 
    // Assuming 32-bit Integer 
    for(int i = 31; i >= 0; i--)                     
    {
         
        // Find current bits in x and y
        int b1 = ((x & (1 << i)) == 0 ) ? 0 : 1;  
        int b2 = ((y & (1 << i)) == 0 ) ? 0 : 1;  
 
        // If both are 1 then 0 else xor is same as OR
        int xoredBit = ((b1 & b2) != 0) ? 0 : (b1 | b2);          
 
        // Update result
        res <<= 1;
        res |= xoredBit;
    }
    return res;
}
 
// Driver Code
public static void main (String[] args)
{
    int x = 3, y = 5;
     
    System.out.println("XOR is " + myXOR(x, y));
}
}
 
// This code is contributed by math_lover

Python3

# Python3 program to find XOR without using ^
 
# Returns XOR of x and y
def myXOR(x, y):
    res = 0 # Initialize result
 
    # Assuming 32-bit Integer
    for i in range(31, -1, -1):
         
        # Find current bits in x and y
        b1 = x & (1 << i)
        b2 = y & (1 << i)
        b1 = min(b1, 1)
        b2 = min(b2, 1)
 
        # If both are 1 then 0 
        # else xor is same as OR
        xoredBit = 0
        if (b1 & b2):
            xoredBit = 0
        else:
            xoredBit = (b1 | b2)
 
        # Update result
        res <<= 1;
        res |= xoredBit
    return res
 
# Driver Code
x = 3
y = 5
print("XOR is", myXOR(x, y))
 
# This code is contributed by Mohit Kumar

C#

// C# program to find XOR
// without using ^
using System;
class GFG{
   
// Returns XOR of x and y
static int myXOR(int x, 
                 int y)
{    
  // Initialize result
  int res = 0; 
 
  // Assuming 32-bit int 
  for(int i = 31; i >= 0; i--)                     
  {
    // Find current bits in x and y
    int b1 = ((x & (1 << i)) == 0 ) ?
               0 : 1;  
    int b2 = ((y & (1 << i)) == 0 ) ? 
               0 : 1;  
 
    // If both are 1 then 0 else 
    // xor is same as OR
    int xoredBit = ((b1 & b2) != 0) ?
                     0 : (b1 | b2);          
 
    // Update result
    res <<= 1;
    res |= xoredBit;
  }
  return res;
}
 
// Driver Code
public static void Main(String[] args)
{
  int x = 3, y = 5;
  Console.WriteLine("XOR is " +
                     myXOR(x, y));
}
}
 
// This code is contributed by 29AjayKumar

Javascript

<script>
 
// JavaScript program to find XOR without using ^
 
// Returns XOR of x and y
function myXOR(x, y)
{
    let res = 0; // Initialize result
     
    // Assuming 32-bit Integer 
    for (let i = 31; i >= 0; i--)                     
    {
    // Find current bits in x and y
      let b1 = ((x & (1 << i)) == 0 ) ? 0 : 1;  
      let b2 = ((y & (1 << i)) == 0 ) ? 0 : 1;  
         
        // If both are 1 then 0 else xor is same as OR
        let xoredBit = (b1 & b2) ? 0 : (b1 | b2);         
 
        // Update result
        res <<= 1;
        res |= xoredBit;
    }
    return res;
}
 
// Driver program to test above function
 
let x = 3, y = 5;
document.write("XOR is " + myXOR(x, y));
 
// This code is contributed by Surbhi Tyagi.
 
</script>

Output

XOR is 6

Time Complexity: O(num), where num is the number of bits in the maximum of the two numbers.
Auxiliary Space: O(1)

Thanks to Utkarsh Trivedi for suggesting this solution.

A Better Solution can find XOR without using a loop.
1) Find bitwise OR of x and y (Result has set bits where either x has set or y has set bit). OR of x = 3 (011) and y = 5 (101) is 7 (111)
2) To remove extra set bits find places where both x and y have set bits. The value of the expression “~x | ~y” has 0 bits wherever x and y both have set bits.
3) bitwise AND of “(x | y)” and “~x | ~y” produces the required result.

Below is the implementation.

C++

// C++ program to find XOR without using ^
#include <iostream>
using namespace std;
 
// Returns XOR of x and y
int myXOR(int x, int y)
{
   return (x | y) & (~x | ~y);
}
 
// Driver program to test above function
int main()
{
   int x = 3, y = 5;
   cout << "XOR is " << myXOR(x, y);
   return 0; 
}

Java

// Java program to find
// XOR without using ^
import java.io.*;
 
class GFG 
{
 
// Returns XOR of x and y
static int myXOR(int x, int y)
{
    return (x | y) & 
           (~x | ~y);
}
 
// Driver Code
public static void main (String[] args) 
{
    int x = 3, y = 5;
    System.out.println("XOR is "+ 
                      (myXOR(x, y)));
}
}
 
// This code is contributed by ajit

Python3

# Python 3 program to 
# find XOR without using ^
 
# Returns XOR of x and y
def myXOR(x, y):
    return ((x | y) & 
            (~x | ~y))
 
# Driver Code
x = 3
y = 5
print("XOR is" , 
       myXOR(x, y))
 
# This code is contributed
# by Smitha

C#

// C# program to find
// XOR without using ^
using System;
 
class GFG
{
     
// Returns XOR of x and y
static int myXOR(int x, int y)
{
    return (x | y) & 
           (~x | ~y);
}
 
// Driver Code
static public void Main ()
{
    int x = 3, y = 5;
    Console.WriteLine("XOR is "+ 
                     (myXOR(x, y)));
}
}
 
// This code is contributed by m_kit

PHP

<?php
// PHP program to find 
// XOR without using ^
 
// Returns XOR of x and y
function myXOR($x, $y)
{
    return ($x | $y) & (~$x | ~$y);
}
 
// Driver Code
$x = 3;
$y = 5;
 
echo "XOR is " , myXOR($x, $y);
 
// This code is contributed by aj_36
?>

Javascript

<script>
// Javascript program to find XOR without using ^
 
// Returns XOR of x and y
function myXOR(x, y)
{
   return (x | y) & (~x | ~y);
}
 
// Driver program to test above function
   let x = 3, y = 5;
   document.write("XOR is " + myXOR(x, y));
 
// This code is contributed by subham348.
</script>

Output

XOR is 6

Time Complexity: O(1) i.e. simple calculation of arithmetic and bitwise operator.
Auxiliary Space: O(1)

Thanks to jitu_the_best for suggesting this solution.

Alternate Solution :

C++

// C++ program to find XOR without using ^
#include <iostream>
using namespace std;
 
// Returns XOR of x and y
int myXOR(int x, int y)
{
   return (x & (~y)) | ((~x )& y);
}
 
// Driver program to test above function
int main()
{
   int x = 3, y = 5;
   cout << "XOR is " << myXOR(x, y);
   return 0; 
}

Java

// Java program to find XOR without using ^
import java.io.*;
  
class GFG 
{
 
// Returns XOR of x and y
static int myXOR(int x, int y)
{
return (x & (~y)) | ((~x )& y);
}
 
// Driver Code
public static void main (String[] args) 
{
  
int x = 3, y = 5;
System.out.println("XOR is "+ 
                      (myXOR(x, y)));
} 
}
 
// This code is contributed by shivanisinghss2110

Python3

# Python3 program to 
# Returns XOR of x and y
def myXOR(x, y):
    return (x & (~y)) | ((~x )& y)
 
# Driver Code
x = 3
y = 5
print("XOR is" , 
    myXOR(x, y))
 
# This code is contributed by shivanisinghss2110

C#

// C# program to find XOR without using ^
using System;
 
class GFG{
 
// Returns XOR of x and y
static int myXOR(int x, int y)
{
    return (x & (~y)) | ((~x )& y);
}
 
// Driver program to test above function
public static void Main()
{
    int x = 3, y = 5;
    Console.WriteLine("XOR is " +myXOR(x, y));
} 
}
 
// This code is contributed by shivansinghss2110

Javascript

<script>
 
// Javascript program to find XOR without using ^
 
// Returns XOR of x and y
function myXOR(x, y)
{
   return (x & (~y)) | ((~x ) & y);
}
 
// Driver code
let x = 3, y = 5;
 
document.write("XOR is " + myXOR(x, y));
 
// This code is contributed by subhammahato348
 
</script>

Output

XOR is 6

Time Complexity: O(1) i.e. simple calculation of arithmetic and bitwise operator.
Auxiliary Space: O(1)

Another Solution: we can simply use one of the properties of the XOR bitwise operator i.e. a+b = a^b + 2*(a&b), with the help of this we can do the same for an operator variant also.

C++14

// C++ program to find XOR without using ^
#include <iostream>
using namespace std;
 
int XOR(int x, int y) { return (x + y - (2 * (x & y))); }
 
int main()
{
    int x = 3, y = 5;
    cout << XOR(x, y) << endl;
    return 0;
}
// this code is contributed by vishu05

Java

// Java program to find XOR without using ^
 
class GFG {
 
    static int XOR(int x, int y) {
        return (x + y - (2 * (x & y)));
    }
 
    public static void main(String[] args) {
        int x = 3, y = 5;
        System.out.print(XOR(x, y) + "\n");
    }
}
 
// This code is contributed by umadevi9616 

Python3

# Python3 program to return XOR of x and y without ^ operator
def XOR(x, y):
    return (x+y - (2*(x & y)))
 
 
# Driver Code
x = 3
y = 5
print("XOR of",x,'&',y,'is:',
      XOR(x, y))
 
# This code is contributed by vishu05

C#

// C# program to find XOR without using ^
using System;
 
class GFG{
 
static int XOR(int x, int y) 
{
    return(x + y - (2 * (x & y)));
}
 
// Driver code
public static void Main(String[] args)
{
    int x = 3, y = 5;
   
    Console.Write(XOR(x, y) + "\n");
}
}
 
// This code is contributed by gauravrajput1

Javascript

<script>
// javascript program to find XOR without using ^
   function XOR(x , y) {
        return (x + y - (2 * (x & y)));
    }
 
     
        var x = 3, y = 5;
        document.write(XOR(x, y) + "\n");
 
// This code contributed by umadevi9616
</script>

Output

Time Complexity: O(1) i.e. simple calculation of arithmetic and bitwise operator.
Auxiliary Space: O(1)

Another Solution: We can simply subtract the AND(&) of the two numbers from the OR(|) so that the common bit gets canceled and the opposite bits remain in the answer.

C++

// C++ program to find XOR without using ^
#include <iostream>
using namespace std;
 
int XOR(int x, int y) { return ((x|y)-(x&y)); }
 
int main()
{
    int x = 3, y = 5;
    cout << XOR(x, y) << endl;
    return 0;
}
// this code is contributed by Suvam Chatterjee

Java

// Java program to find XOR without using ^
 
class GFG {
 
    static int XOR(int x, int y)
    {
        return ((x | y) - (x & y));
    }
 
    public static void main(String[] args)
    {
        int x = 3, y = 5;
        System.out.print(XOR(x, y) + "\n");
    }
}
 
// This code is contributed by garg28harsh.

Python3

# Python program to find XOR without using ^
def XOR(x, y):
    return ((x | y) - (x & y))
 
x, y = 3, 5
print(XOR(x, y))
 
# This code is contributed by lokesh

C#

using System;
class GFG {
  static int XOR(int x, int y)
  {
    return ((x | y) - (x & y));
  }
  public static void Main(String[] args)
  {
 
    int x = 3, y = 5;
    Console.Write(XOR(x, y));
    return;
  }
}
 
// This code is contributed by garg28harsh.

Javascript

// Javascript program to find XOR without using ^
function XOR(x, y) 
{ return ((x | y) - (x & y)); }
 
let x = 3, y = 5;
console.log(XOR(x, y));
 
// This code is contributed by garg28harsh.

Output

Time Complexity: O(1) i.e. simple calculation of arithmetic and bitwise operator.
Auxiliary Space: O(1)

Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.

Recommended

Solve DSA problems on GfG Practice.

Solve Problems

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!

Find XOR of two number without using XOR operator

C++

C

Java

Python3

C#

Javascript

C++

Java

Python3

C#

PHP

Javascript

C++

Java

Python3

C#

Javascript

C++14

Java

Python3

C#

Javascript

C++

Java

Python3

C#

Javascript

LEAVE A REPLY Cancel reply

Most Popular

Recent Comments

EDITOR PICKS

POPULAR POSTS

POPULAR CATEGORY

ABOUT US

FOLLOW US