$XOR$ of random permutations of numbers

Question

A question from the CodeChef December Long Challenge:

Given two binary numbers $A$ and $B$, each with $N$ bits. We may reorder the bits of $A$ in an arbitrary way, and at the same time reorder the bits of $B$ in an arbitrary (not necessarily the same) way. Then, compute the $XOR$ of the resulting permutations. Find the number of distinct values of this $XOR$ which can be obtained.

$N\leq 10^6$, and so, the method should be $O(N)$.

Example:

$A = 10, B = 01$

Possible permutations = $(10, 01), (10, 10), (01, 01), (01, 10)$. Corresponding $XORs = 11, 00, 00, 11$. Hence, answer = $2$.

---

My solution:

I'm able to solve a very specific case. Let $n_a$ and $n_b$ be the number of $1$s in $A$ and $B$. If $n_a = 0$, answer would be simply the number of permutations (when I say permutations, I mean the permutation of places that the ones can occupy) of $B = {N\choose {n_b}}$. Similar is the case when $n_b = 0$. I also observed that if we fix $A$, it will never result in the same XOR with any permutation of B as:

$$a\text{ }XOR\text{ }b_1=a\text{ }XOR\text{ }b_2=> b_1=b_2$$which can't be the case since $b_1$ and $b_2$ are different permutations (in the position of 1s). I tried it for the more general case too:

$$a_1\text{ }XOR\text{ }b_1=a_2\text{ }XOR\text{ }b_2=> a_1\text{ }XOR\text{ }a_2=b_1\text{ }XOR\text{ }b_2$$but I don't know what to do next!?

As a summary, I most likely should get a formula in $n_a$ and $n_b$, but I'm unable to reach there. Any help would be nice!

Answer 1

The answer only depends on $n_a, n_b$, not on the numbers themselves because you can permute the bits. You need to consider what is the minimum and maximum number of $1$s that can occur in the XOR.

The minimum comes when you match up as many $1$s as possible, which happens if both numbers start off with all their $1$s and follow with all their $0$s. That will give us $n_{\min}=|n_a-n_b|\ 1$s in the XOR.

The maximum comes when we match up as few $1$s as possible, which will happen when the permutation of $a$ starts with all $1$s and the permutation of $b$ ends with all $1$s. If $n_a+n_b\le N,$ we will get $n_a+n_b\ 1$s in the XOR. If $n_a+n_b \gt N$ the $1$s will overlap in the middle and we will get $n_a+n_b-N\ 0$s from that, so there will be $n_{\max}=2N-n_a-n_b\ 1$s.

Finally you need to add up how many numbers there are with this many $1$s. This gives $$\sum_{k=n_{\min}\\ \text{step 2}}^{n_{\max}}{N \choose k}$$

Answer 2

Let $A$, $B$ be $2$ $N$-bit integers. Let $a$ be the number of $1$s in $A$'s expansion, and $b$ the number of $1$s in $B$'s expansion (WLOG $0\leq a\leq b\leq N$).

The minimum number of $1$ bits, which we will call $x$, in $A\otimes B$ ($\otimes$ is XOR) is $b-a$, and the maximum number is $$m_n(a,b)=\begin{cases}2N-a-b&a+b>N\\a+b&a+b\leq N\end{cases}$$ Note that $\forall k\in\mathbb N\cup\{0\}$ such that $2k\leq m_n(a,b)-b+a$, $2k+b-a$ is a possible number of $1$s to result from $A\otimes B$. And, any permutation of these $1$s is possible. You can take it from here.