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++
#include <iostream>
using namespace std;
int myXOR(int x, int y)
{
int res = 0;
for (int i = 31; i >= 0; i--)
{
bool b1 = x & (1 << i);
bool b2 = y & (1 << i);
bool xoredBit = (b1 & b2) ? 0 : (b1 | b2);
res <<= 1;
res |= xoredBit;
}
return res;
}
int main()
{
int x = 3, y = 5;
cout << "XOR is " << myXOR(x, y);
return 0;
}
|
C
#include <stdio.h>
#include <stdbool.h> //to use bool
int myXOR(int x, int y)
{
int res = 0;
for (int i = 31; i >= 0; i--)
{
bool b1 = x & (1 << i);
bool b2 = y & (1 << i);
bool xoredBit = (b1 & b2) ? 0 : (b1 | b2);
res <<= 1;
res |= xoredBit;
}
return res;
}
int main()
{
int x = 3, y = 5;
printf("XOR is %d\n", myXOR(x, y));
return 0;
}
|
Java
import java.io.*;
class GFG{
static int myXOR(int x, int y)
{
int res = 0;
for(int i = 31; i >= 0; i--)
{
int b1 = ((x & (1 << i)) == 0 ) ? 0 : 1;
int b2 = ((y & (1 << i)) == 0 ) ? 0 : 1;
int xoredBit = ((b1 & b2) != 0) ? 0 : (b1 | b2);
res <<= 1;
res |= xoredBit;
}
return res;
}
public static void main (String[] args)
{
int x = 3, y = 5;
System.out.println("XOR is " + myXOR(x, y));
}
}
|
Python3
def myXOR(x, y):
res = 0
for i in range(31, -1, -1):
b1 = x & (1 << i)
b2 = y & (1 << i)
b1 = min(b1, 1)
b2 = min(b2, 1)
xoredBit = 0
if (b1 & b2):
xoredBit = 0
else:
xoredBit = (b1 | b2)
res <<= 1;
res |= xoredBit
return res
x = 3
y = 5
print("XOR is", myXOR(x, y))
|
C#
using System;
class GFG{
static int myXOR(int x,
int y)
{
int res = 0;
for(int i = 31; i >= 0; i--)
{
int b1 = ((x & (1 << i)) == 0 ) ?
0 : 1;
int b2 = ((y & (1 << i)) == 0 ) ?
0 : 1;
int xoredBit = ((b1 & b2) != 0) ?
0 : (b1 | b2);
res <<= 1;
res |= xoredBit;
}
return res;
}
public static void Main(String[] args)
{
int x = 3, y = 5;
Console.WriteLine("XOR is " +
myXOR(x, y));
}
}
|
Javascript
<script>
function myXOR(x, y)
{
let res = 0;
for (let i = 31; i >= 0; i--)
{
let b1 = ((x & (1 << i)) == 0 ) ? 0 : 1;
let b2 = ((y & (1 << i)) == 0 ) ? 0 : 1;
let xoredBit = (b1 & b2) ? 0 : (b1 | b2);
res <<= 1;
res |= xoredBit;
}
return res;
}
let x = 3, y = 5;
document.write("XOR is " + myXOR(x, y));
</script>
|
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++
#include <iostream>
using namespace std;
int myXOR(int x, int y)
{
return (x | y) & (~x | ~y);
}
int main()
{
int x = 3, y = 5;
cout << "XOR is " << myXOR(x, y);
return 0;
}
|
Java
import java.io.*;
class GFG
{
static int myXOR(int x, int y)
{
return (x | y) &
(~x | ~y);
}
public static void main (String[] args)
{
int x = 3, y = 5;
System.out.println("XOR is "+
(myXOR(x, y)));
}
}
|
Python3
def myXOR(x, y):
return ((x | y) &
(~x | ~y))
x = 3
y = 5
print("XOR is" ,
myXOR(x, y))
|
C#
using System;
class GFG
{
static int myXOR(int x, int y)
{
return (x | y) &
(~x | ~y);
}
static public void Main ()
{
int x = 3, y = 5;
Console.WriteLine("XOR is "+
(myXOR(x, y)));
}
}
|
PHP
<?php
function myXOR($x, $y)
{
return ($x | $y) & (~$x | ~$y);
}
$x = 3;
$y = 5;
echo "XOR is " , myXOR($x, $y);
?>
|
Javascript
<script>
function myXOR(x, y)
{
return (x | y) & (~x | ~y);
}
let x = 3, y = 5;
document.write("XOR is " + myXOR(x, y));
</script>
|
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++
#include <iostream>
using namespace std;
int myXOR(int x, int y)
{
return (x & (~y)) | ((~x )& y);
}
int main()
{
int x = 3, y = 5;
cout << "XOR is " << myXOR(x, y);
return 0;
}
|
Java
import java.io.*;
class GFG
{
static int myXOR(int x, int y)
{
return (x & (~y)) | ((~x )& y);
}
public static void main (String[] args)
{
int x = 3, y = 5;
System.out.println("XOR is "+
(myXOR(x, y)));
}
}
|
Python3
def myXOR(x, y):
return (x & (~y)) | ((~x )& y)
x = 3
y = 5
print("XOR is" ,
myXOR(x, y))
|
C#
using System;
class GFG{
static int myXOR(int x, int y)
{
return (x & (~y)) | ((~x )& y);
}
public static void Main()
{
int x = 3, y = 5;
Console.WriteLine("XOR is " +myXOR(x, y));
}
}
|
Javascript
<script>
function myXOR(x, y)
{
return (x & (~y)) | ((~x ) & y);
}
let x = 3, y = 5;
document.write("XOR is " + myXOR(x, y));
</script>
|
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
#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;
}
|
Java
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");
}
}
|
Python3
def XOR(x, y):
return (x+y - (2*(x & y)))
x = 3
y = 5
print("XOR of",x,'&',y,'is:',
XOR(x, y))
|
C#
using System;
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;
Console.Write(XOR(x, y) + "\n");
}
}
|
Javascript
<script>
function XOR(x , y) {
return (x + y - (2 * (x & y)));
}
var x = 3, y = 5;
document.write(XOR(x, y) + "\n");
</script>
|
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++
#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;
}
|
Java
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");
}
}
|
Python3
def XOR(x, y):
return ((x | y) - (x & y))
x, y = 3, 5
print(XOR(x, y))
|
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;
}
}
|
Javascript
function XOR(x, y)
{ return ((x | y) - (x & y)); }
let x = 3, y = 5;
console.log(XOR(x, y));
|
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.
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!
