Welcome to OGeek Q&A Community for programmer and developer-Open, Learning and Share
Welcome To Ask or Share your Answers For Others

Categories

0 votes
943 views
in Technique[技术] by (71.8m points)

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

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.

See Question&Answers more detail:os

与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
Welcome To Ask or Share your Answers For Others

1 Reply

0 votes
by (71.8m points)

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.


与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
OGeek|极客中国-欢迎来到极客的世界,一个免费开放的程序员编程交流平台!开放,进步,分享!让技术改变生活,让极客改变未来! Welcome to OGeek Q&A Community for programmer and developer-Open, Learning and Share
Click Here to Ask a Question

...