algorithm - Given an XOR and SUM of two numbers, how to find the number of pairs that satisfy them?

Question

I think the question may be a bit confusing. So, I'll try to explain it first.

Let's say the XOR and SUM of two numbers are given. (Note that there are multiple pairs that may satisfy this.)

For example, If the XOR is 5 and the SUM is 9 there are 4 pairs satisfying the SUM and XOR. They are (2,?7), (3,?6), (6,?3), (7,?2). So 2+7=9 and 2^7=5.

I just want to find the number of pairs that satisfies the SUM and XOR. So in the example I mentioned the answer 4 is enough. I don't need to know which pairs satisfy them.

I took this problem from here.

I checked for an answer here. It provides an O(n) solution which is not enough.

There is an Editorial that provides the solution on this problem. It can be found here. (Look for the solution of 627A)

The problem is that I can't understand the solution. From what I could sum up they used a formula like this,
(If there are two numbers a and b) then, a+b = (a XOR b) + (a AND b)*2

How do I arrive to that? The rest of the steps are unclear to me.

If anyone could provide an idea on how to solve this or explain their solution, please help.

Answer 1

Think of a+b = (a XOR b) + (a AND b)*2 as exactly what happen when you do binary addition. From your example, a = 010 and b = 111:

 010
 111
 ---
1001 = 101 + 100

For each bit, you add bits from a and b (0+0=0, 0+1=1, 1+0=1, 1+1=0, which is exactly a XOR b plus the carry-in bit from the previous addition, i.e. if both previous bits for a and b are 1, then we add it also. This is exactly (a AND b)*2. (Remember that multiplication by 2 is a shift left.)

With that equation we can calculate a AND b.

Now to count the number you want, we look at each bits of a XOR b and a AND b one-by-one and multiply all possibilities. (Let me write a[i] for the i-th bit of a)

• If a[i] XOR b[i] = 0 and a[i] AND b[i] = 0, then a[i] = b[i] = 0. Only one possibility for this bit.

• If a[i] XOR b[i] = 0 and a[i] AND b[i] = 1, then a[i] = b[i] = 1. Only one possibility for this bit.

• If a[i] XOR b[i] = 1 and a[i] AND b[i] = 0, then a[i] = 1 and b[i] = 0 or vice versa. Two possibilities.

• It's not possible to have a[i] XOR b[i] = 1 and a[i] AND b[i] = 1.

From your example, a XOR b = 101 and a AND b = 010. We have the answer 2*1*2 = 4.