How to find the numbers from their Sum and XOR values in C++

This tutorial will help all the users to learn How to find the numbers from their Sum and XOR values. Once the user enters the two values, one for sum and the other for XOR, we can calculate the possible numbers that match the given input.  Let us see how the program works. Feel free to ask questions or leave comments in the comments section at the end of the post.

C++ program to find the numbers from their Sum and XOR values

The method is easy and is implemented in steps. COnsider that we treat the numbers in binary form.

Initially, we consider the XOR value entered by the user. Each bit from this value can be examined to generate possible cases. For instance,

if XOR_value[i] = 0 then that means that the ith bits in numbers, that is number1[i] and number2[i] must be same.
This condition produces two cases.

if XOR_value[i] = 1 then that means that the ith bits in numbers, that is number1[i] and number2[i] must be different.
This condition produces two cases.

In such a way, depending upon the number of bits in the XOR value, we can generate (2 ^ n) possible pairs.

 

Now consider a variable p. Here,

Sum = XOR_value + (2*p)

This rule is necessary for an efficient solution.

To back track this calculation, we can find p as,

p = (Sum - XOR_value) / 2

 

After calculating the value for p, using the bits from XOR_value and p, we can find all the bits of number1 and number2. The rules used for this are as follows,

  1. if XOR_value[i] = 0 and p[i] = 0, then number1[i] = number2[i] = 0. Only one possibility.
  2. if XOR_value[i] = 0 and p[i] = 1, then number1[i] = number2[i] = 1. Only one possibility.
  3. if XOR_value[i] = 1 and p[i] = 0, then number1[i] = 1, number2[i] = 0 or number1[i] = 0, number2[i] = 1
    (Either of the case can be considered)
  4. if XOR_value[i] = 1 and p[i] = 1, then the given input does not have any such possible pair of numbers.

1. Input

Code :

unsigned long int sum_value, xor_value;

cout<<"\nEnter the value for Sum : ";
cin>>sum_value;

cout<<"\nEnter the value for XOR : ";
cin>>xor_value;

The user is prompted to enter the values for Sum and XOR which we will be using to do the rest of the calculation.
Both the values are passed to the value() function for further calculation.

Output :

Enter the value for Sum : 16

Enter the value for XOR : 14

 

2. value() function

Code :

void value(unsigned long int sum_value, unsigned long int xor_value)
{
    unsigned long int p = (sum_value - xor_value)/2;

    int num1 = 0, num2 = 0;

    for (int i = 0; i < 8*sizeof(sum_value); i++)
    {
        unsigned long int xi = (xor_value & (1 << i));
        unsigned long int pi = (p & (1 << i));

        if (xi == 0 && pi == 0)
        {

        }
        else if (xi == 0 && pi > 0)
        {
            num1 = ((1 << i) | num1);
            num2 = ((1 << i) | num2);
        }
        else if (xi > 0 && pi == 0)
        {
            num1 = ((1 << i) | num1);
        }
        else
        {
            cout << "No such pair of numbers exists!";
            return;
        }
    }

    cout << "\nNumber 1 : " << num1 << endl << "Number 2 : " << num2;
}

All the above explained rules are applied to check all the conditions and calculate the bits of the pair of numbers that correspond to the entered Sum and XOR values. Please observe the above function carefully to understand how the numbers are calculated. In ideal cases, the two generated numbers are printed on the screen. In cases where the none of the possibilities match with the input, the user is informed that there is no such possible pair of numbers.

 

Complete Code

#include <iostream>
using namespace std;

void value(unsigned long int sum_value, unsigned long int xor_value)
{
    unsigned long int p = (sum_value - xor_value)/2;

    int num1 = 0, num2 = 0;

    for (int i = 0; i < 8*sizeof(sum_value); i++)
    {
        unsigned long int xi = (xor_value & (1 << i));
        unsigned long int pi = (p & (1 << i));

        if (xi == 0 && pi == 0)
        {

        }
        else if (xi == 0 && pi > 0)
        {
            num1 = ((1 << i) | num1);
            num2 = ((1 << i) | num2);
        }
        else if (xi > 0 && pi == 0)
        {
            num1 = ((1 << i) | num1);
        }
        else
        {
            cout << "No such pair of numbers exists!";
            return;
        }
    }

    cout << "\nNumber 1 : " << num1 << endl << "Number 2 : " << num2;
}

int main()
{
    unsigned long int sum_value, xor_value;

    cout<<"\nEnter the value for Sum : ";
    cin>>sum_value;

    cout<<"\nEnter the value for XOR : ";
    cin>>xor_value;

    value(sum_value, xor_value);

    return 0;
}

Output :

Enter the value for Sum : 16

Enter the value for XOR : 14

Number 1 : 15
Number 2 : 1

Therefore, we have learnt How to find the numbers from their Sum and XOR values.

You may also learn,

Operators in C++

Leave a Reply

Your email address will not be published. Required fields are marked *