In this blog post, I will teach you how to write C/C++ program to find XOR of two number without using XOR Operator. After reading this detail guide post I believe you able to write an efficient program to find XOR of two number without using XOR Operator.
Examples:
Input: n1 = 5, n2 = 13 Output: 3
Let’s understand the above example with the help of their binary representation.
Input : n1 = 5 Here's a simple ASCII representation of 5 (an 8-bit integer): 7 6 5 4 3 2 1 0 (Bit position) +---+---+---+---+---+---+---+---+ | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 1 | (Example bit values) +---+---+---+---+---+---+---+---+ Input : n2 = 13 Here's a simple ASCII representation of 5 (an 8-bit integer): 7 6 5 4 3 2 1 0 (Bit position) +---+---+---+---+---+---+---+---+ | 0 | 0 | 0 | 0 | 1 | 1 | 0 | 1 | (Example bit values) +---+---+---+---+---+---+---+---+ Now, n1 EX-OR n2 Output: 8 Here's a simple ASCII representation of 8 (an 8-bit integer): 7 6 5 4 3 2 1 0 (Bit position) +---+---+---+---+---+---+---+---+ | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | (Example bit values) +---+---+---+---+---+---+---+---+
Let’s see the problem statements for this question.
Problem Statement: Given two integers, n1 and n2, the task is to find their XOR without using the XOR operator. i.e., without using ‘^’ in C/C++.
Disclaimer: Try to solve the problem yourself first otherwise it would be not worth solving this problem
Approach-1: Naive approach to find XOR of two number without using XOR Operator:
In the naive approach, we just follow the same concept which XOR Operator (^) does. i.e,
1. If the bits at the ith position are the same, we put 0 at that position.
2. Else if the bits at the ith position are different, we put 1 at that position.
C program to Find XOR of two number without using XOR Operator:
/*
C program to find XOR of two
number without using XOR Operator ^
*/
#include <stdio.h>
//to use bool
#include <stdbool.h>
#define BITS_IN_INT sizeof(int)*8
//Make it 0 to enable second naive approach
#if 1
// Returns XOR of n1 and n2
int myXOR(int n1, int n2)
{
int ret = 0; // Initialize result
for (int i = (BITS_IN_INT-1); i >= 0; i--)
{
// Find current bits in n1 and n2
bool b1 = n1 & (1 << i);
bool b2 = n2 & (1 << i);
// If both are 1 then 0 else xor is same as OR
bool xoredBit = (b1 & b2) ? 0 : (b1 | b2);
// Update result
ret <<= 1;
ret |= xoredBit;
}
return ret;
}
#else
int myXOR(int n1, int n2)
{
int ret = 0;
for (int i = 0; i < BITS_IN_INT; i++)
{
if (((1LL << i) & n1) != ((1LL << i) & n2))
{
ret |= (1LL << i);
}
}
return ret;
}
#endif
int main()
{
int n1 = 5, n2 = 13;
const unsigned int n1XORn2 = myXOR(n1,n2);
printf("XOR is %d\n", n1XORn2);
return 0;
}
Output: XOR is 8
C++ program to Find XOR of two number without using XOR Operator:
/*
C program to find XOR of two
number without using XOR Operator ^
*/
#include <iostream>
//Bits in integer
#define BITS_IN_INT sizeof(int)*8
//Make it 1 to enable first naive approach
#if 0
// Returns XOR of n1 and n2
int myXOR(int n1, int n2)
{
int ret = 0; // Initialize result
for (int i = (BITS_IN_INT-1); i >= 0; i--)
{
// Find current bits in n1 and n2
bool b1 = n1 & (1 << i);
bool b2 = n2 & (1 << i);
// If both are 1 then 0 else xor is same as OR
bool xoredBit = (b1 & b2) ? 0 : (b1 | b2);
// Update result
ret <<= 1;
ret |= xoredBit;
}
return ret;
}
#else
int myXOR(int n1, int n2)
{
int ret = 0;
for (int i = 0; i < BITS_IN_INT; i++)
{
if (((1LL << i) & n1) != ((1LL << i) & n2))
{
ret |= (1LL << i);
}
}
return ret;
}
#endif
int main()
{
int n1 = 5, n2 = 13;
const unsigned int n1XORn2 = myXOR(n1,n2);
std::cout<<"XOR is "<< n1XORn2 <<std::endl;
return 0;
}
Output: XOR is 8
Approach-2: Using bitwise operators:
This approach is an optimize way in which you can find XOR without using a loop. You need to follow the following steps to get the XOR.
Step-1. First find all the bits where either ‘n1‘ or ‘n2‘ bits are set. You can get it by doing Oring between n1 and n2 (n1|n2).
Step-2. In the second steps you need to remove those set bits where both ‘n1‘ and ‘n2‘ are set. You can achieve this by ~n1 | ~n2 (performs a bitwise OR operation between the bitwise negations of n1 and n2).
Step-3. In the last you need to do Bitwise AND between the expressions what you have get in step 1 and 2 ((n1 | n2) & (~n1 | ~n2)) to get the desired result.
C program to Find XOR of two number without using XOR Operator and loop:
/*
C program to find XOR of two
number without using XOR Operator ^
*/
#include <stdio.h>
// Returns XOR of n1 and n2
int myXOR(int n1, int n2)
{
return (n1 | n2) & (~n1 | ~n2);
}
int main()
{
int n1 = 5, n2 = 13;
const unsigned int n1XORn2 = myXOR(n1,n2);
printf("XOR is %d\n", n1XORn2);
return 0;
}
Output: XOR is 8
- Time Complexity: O(1) i.e. simple calculation of arithmetic and bitwise operator.
- Auxiliary Space: O(1)
C++ program to Find XOR of two number without using XOR Operator and loop:
/*
C program to find XOR of two
number without using XOR Operator ^
*/
#include <iostream>
// Returns XOR of n1 and n2
int myXOR(int n1, int n2)
{
return (n1 | n2) & (~n1 | ~n2);
}
int main()
{
int n1 = 5, n2 = 13;
const unsigned int n1XORn2 = myXOR(n1,n2);
std::cout<<"XOR is "<< n1XORn2 <<std::endl;
return 0;
}
Output: XOR is 8
- Time Complexity: O(1) i.e. simple calculation of arithmetic and bitwise operator.
- Auxiliary Space: O(1)
There is also one another solution to get the XOR of two numbers without XOR operator and loop. Consider the below code,
C code:
/*
C program to find XOR of two
number without using XOR Operator ^
*/
#include <stdio.h>
// Returns XOR of n1 and n2
int myXOR(int n1, int n2)
{
return (n1 & (~n2))|((~n1) & n2);
}
int main()
{
int n1 = 5, n2 = 13;
const unsigned int n1XORn2 = myXOR(n1,n2);
printf("XOR is %d\n", n1XORn2);
return 0;
}
Output: XOR is 8
Complexity Analysis:
Time Complexity: O(1)
Space Complexity: O(1)
C++ code:
/*
C program to find XOR of two
number without using XOR Operator ^
*/
#include <iostream>
// Returns XOR of n1 and n2
int myXOR(int n1, int n2)
{
return (n1 & (~n2))|((~n1) & n2);
}
int main()
{
int n1 = 5, n2 = 13;
const unsigned int n1XORn2 = myXOR(n1,n2);
std::cout<<"XOR is "<< n1XORn2 <<std::endl;
return 0;
}
Approach-3: (Using the XOR-AND-SUM Property)
You can simply use one of the well-known properties of XOR, i.e. ( n1+n2 = n1^n2 + 2*(n1&n2). With the help of this you can find XOR between n1 and n2.
C code Using the XOR-AND-SUM Property:
/*
C program to find XOR of two
number without using XOR Operator ^
*/
#include <stdio.h>
// Returns XOR of n1 and n2
int myXOR(int n1, int n2)
{
return (n1 + n2) - (2 * (n1 & n2));
}
int main()
{
int n1 = 5, n2 = 13;
const unsigned int n1XORn2 = myXOR(n1,n2);
printf("XOR is %d\n", n1XORn2);
return 0;
}
Output: XOR is 8
Complexity Analysis:
Time Complexity: O(1)
Space Complexity: O(1)
C++ code Using the XOR-AND-SUM Property:
/*
C program to find XOR of two
number without using XOR Operator ^
*/
#include <iostream>
// Returns XOR of n1 and n2
int myXOR(int n1, int n2)
{
return (n1 + n2) - (2 * (n1 & n2));
}
int main()
{
int n1 = 5, n2 = 13;
const unsigned int n1XORn2 = myXOR(n1,n2);
std::cout<<"XOR is "<< n1XORn2 <<std::endl;
return 0;
}
Recommended Post
- toggle the particular bits in given number.
- How to Set a Particular Bit in a number.
- turn off a particular bit.
- Count Set bits in an Integer.
- Turn off the rightmost set bit.
- Rotate bits of a number.
- Macros for Bit Manipulation in C/C++.
- 5 Ways to Check if Two Integers have Opposite Signs.
- Operator Precedence And Associativity In C.
- Operators in C language
