0

I have two sets of whole numbers $\{s_1,s_2,s_3, \dotsc,s_n \}$ and $\{p_1,p_2,p_3, \dotsc, p_m\}$. Now I will take a number from first set, and XOR it with some number from set 2, and I want to find the sum of all the possible combinations.

For example, if $s_1=\{1,2,3\}$ and $s_2=\{2,1\}$:

the sum would be: $1 \wedge 2 + 1\wedge 1 + 2\wedge 2 + 2\wedge 1 + 3\wedge 2 + 3\wedge 1$, ('+' is regular addition and not binary OR) $= 3+0+0+3+1+2=9$.

EDIT: I can obviously do it using brute force, i.e. find the XOR of each pair first and add them, but is there an efficient way?

mvw
  • 34,562
aroma
  • 482
  • 4
  • 12

1 Answers1

0

Suppose you represent each number as a string of $d$ bits. Consider the $i$th bit and let $n_i$ be the # of numbers in $\{s_1, s_2, \cdots, s_n\}$ whose $i$th bits are $1$ and $m_i$ be the # of numbers in $\{p_1, p_2, \cdots, p_m\}$ whose $i$th bits are $1$. Then we can know that the $i$th bit contributes $$ \left\{(n - n_i)m_i + n_i(m - m_i)\right\}\cdot 2^{i-1} $$ to the final result because $(n - n_i)m_i + n_i(m - m_i)$ is the # of numbers in the multiset $\{s_i \land p_j\}$ whose $i$th bits are $1$. Therefore, the final result would be $$ \sum_{i=1}^d\left\{(n - n_i)m_i + n_i(m - m_i)\right\}\cdot 2^{i-1} $$ It is a more efficient way because it requires only $\mathcal{O}(d(m + n))$ operations while brute force needs however $\Omega(mn)$ operations.

PSPACEhard
  • 10,283