Find XOR of two number without using XOR Operator

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