Can I simplify successive XOR operations?

Question

I'm doing an online programming challenge where successive XOR operations are used (from codewars.com, if you don't want to create an account, here are the instructions).

We have a rectangle of known dimensions where every value of column and row (zero-indexed) are XOR-ed in order to create a value. Then, we must compute the sum of every value of that rectangle. (i.e. for a rectange of 8 columns & 5 rows, the first value would be 0 ^ 0 = 0, then 0 ^ 1 = 1, etc. until 7 ^ 4 = 3, then the sum of every value would give 105, which is the result)

I've tried different approach to this problem, but every one of them end up being too slow and not enough efficient. The naive solution is of time complexity $O(N^2)$, which becomes too slow when we're working with a lot of values.

Here would be the function to compute the value of 1 row. (x is the number of columns & y is the number of the current row) $$ f(x,y) = (0 \oplus y) + (1 \oplus y) + (2 \oplus y) + (3 \oplus y) + .. + ((x - 1) \oplus y) $$ So the whole rectangle would be that function from 0 to y - 1 for the y value.

So my question is: Is there a way where I can simplify a function like that to gain efficiency ?

Answer 1

Yes, there are ways to improve the efficiency greatly.

---

Let ${}_k{i}$ be the $k$-th digit of $i$ in binary representation, i.e., it is 0 if $\lfloor i/2^k\rfloor$ is even and 1 otherwise. For example, since $19=(10011)_2$, $_019=1$, $_119=1$, $_219=0$, $_319=0$, $_419=1$. In most programming languages, ${}_k{i}$ can be computed as $(i\text{>>}k)\%2$.

Let us apply the power of summand splitting and rearrangement to inspect the contribution to the sum by the $k$-th digits in isolation.

$$\begin{aligned} \text{total sum} &=\sum_{\text{ row } i\,}\sum_{\text{ column }j\,} i \oplus j\\ &=\sum_{\text{ row } i\,}\sum_{\text{ column }j\,} \sum_{0\le k\lt u} ({}_k{i}\oplus {}_k{j})\cdot 2^k\\ &=\sum_{0\le k\lt u} 2^k\sum_{\text{ row } i\,}\sum_{\text{ column }j\,} {}_k{i}\oplus {}_k{j}\\ &=\sum_{0\le k\lt u} 2^k\left(\#\{\text{row }i\mid {}_k{i}=1\}\cdot \#\{\text{column }j\mid {}_k{j}=0\}\right.\ + \\ &\quad\quad\left.\#\{\text{row }i\mid {}_k{i}=0\}\cdot \#\{\text{column }j\mid {}_k{j}=1\}\right) \end{aligned}$$

We can set $u=\lceil\log_2\max(m+1, n+1)\rceil$ or any integer such that $n,m\lt 2^u$, where $n$ is the number of rows and $m$ is the number of columns. If $m$ and $n$ are ints or longs in Java or C#, $u=63$ could be a good choice.

Now the problem is shifted to compute $\#\{\text{row }i\mid {}_k{i}=0\}$ and the like ones. We have $$\begin{aligned} \#\{\text{row }i\mid {}_k{i}=0\} &=2^k\left\lfloor\frac {n-1}{2^{k+1}}\right\rfloor + \min\left(n-2^{k+1}\left\lfloor\frac{n-1}{2^{k+1}}\right\rfloor,\ 2^k\right)\\ \#\{\text{row }i\mid {}_k{i}=1\} &=2^k\left\lfloor\frac{n-1}{2^{k+1}}\right\rfloor + \max\left(0,\ n-2^{k+1}\left\lfloor\frac{n-1}{2^{k+1}}\right\rfloor -2^k\right) \end{aligned}$$ In terms of Java, they are, respectively,

((n-1)>>(k+1)<<k) + Math.min(1<<k, n - ((n-1)>>(k+1)<<(k+1))),
((n-1)>>(k+1)<<k) + Math.max(0, n - ((n - 1)>>(k+1)<<(k+1)) - (1<<k))

The time-complexity of the algorithm is about $O((\log n)^2)$