Count of possible pairs whose sum and bitwise XOR is given

Given two integers S and X representing the sum and bitwise XOR respectively of two integers, the task is to find the count of all such possible pairs such that their sum is equal to S and bitwise XOR is equal to X.

Examples:

Input: S = 9, X = 5
Output: 4
Explanation: (2, 7), (3, 6), (6, 3), (7, 2) completely satisfies the given conditions.
It can also be seen that no other pair satisfy the given condition.
So the total possibility is 4.

Input: S = 3, X = 3
Output: 4
Explanation: Only (1, 2), (2, 1), (3, 0) and (0, 3) satisfy the given condition.

Approach: The solution to the problem is based on the following observation:

Consider two nnumbers a and b. Their sum can be written as
a+b = (a XOR b) + (a AND b)*2

The above can be proved as follows:
If two bits x and y are added, the carry (say c) will be (x AND y) and it is to one position left of the single bit. So, c = 2 * (x AND y)
The value of the rightmost bit (i.e., at the same position as of the single bits) will be (x XOR y)
Therefore x + y = (x XOR y) + 2 * (x AND y)

So when adding a and b, this procedure repeats for each bit. Therefore it can be said that the sum will be 
a+b = (a XOR b) + (a AND b)*2 
S = X + 2*A   where A is the bitwise AND of the two numbers.
A = (S – X)/2

Based on the above observation the count can be obtained from the bit values of A and X as per the following case

  • If the ith bit of X and A both are 0, then there is only one possible pair for that bit position.
  • If the ith bit of X is 1 and of A is 0, then there are two possible pairs for that bit position.
  • If the ith bit of X is 0 and of A is 1, then there is only one possible pair for that bit position.
  • There cannot be a situation wher ith bit at X is 1 and ith bit of A is also 1.

According to the multiplication principle of permutation, to get the number of possible pairs satisfying the given condition just multiply all possibilities. Follow the steps mentioned below to implement the idea:

  • Find bitwise AND of two numbers by using the above formula.
  • If it is not an integer then no solution exist 
  • Otherwise for given value of the XOR (X) and AND (say A) check for each bit 
    • Find the number of possibilities for that bit using the above cases.
    • Multiply these possibilities with the final answer. 
  • At the end the total number possibilities calculated as per the above conditions is the required answer.

   Below is the implementation of the above approach.

C++

  

#include <bits/stdc++.h>

using namespace std;

  

int count_all_possible_pair(int sum_value,

                            int xor_value)

{

    double and_value

        = ((sum_value - xor_value) / 2.0);

  

    

    

    int check = and_value;

    if (check != and_value)

        return 0;

  

    int count = 1;

  

    

    

    for (int i = 1; i <= 32; i++) {

        int and_bit = (check >> i) & 1;

        int xor_bit = (xor_value >> i) & 1;

  

        

        if (and_bit == 0 && xor_bit == 0)

            count = count * 1;

  

        

        

        else if (xor_bit == 0 && and_bit == 1)

            count = count * 1;

  

        

        

        else if (xor_bit == 1 && and_bit == 0)

            count = count * 2;

  

        

        

        else

            return 0;

    }

  

    

    return count;

}

  

int main()

{

    int S = 9, X = 5;

  

    

    cout << count_all_possible_pair(S, X);

    return 0;

}

Time Complexity: O(N) where N is the number of bits in the given sum S
Auxiliary Space: O(1)

By Julio MarchiPosted on