Given an XOR and SUM of two numbers, how to find the number of pairs that satisfy them?
<p>I think the question may be a bit confusing. So, I'll try to explain it first.</p>

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

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

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

<p>I took this problem from <a href="http://codeforces.com/problemset/problem/627/A" rel="noreferrer">here</a>. </p>

<p>I checked for an answer <a href="https://stackoverflow.com/questions/18732329/given-xor-sum-of-two-numbers-how-to-find-the-numbers">here</a>. It provides an O(n) solution which is not enough.</p>

<p>There is an Editorial that provides the solution on this problem. It can be found <a href="http://codeforces.com/blog/entry/43467" rel="noreferrer">here</a>. (Look for the solution of 627A)</p>

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

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

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