Compute the XOR of all the elements in the upper left triangular of a square matrix

Given a dimension \$D\$. We generate a \$D\times D\$ matrix with elements that start from \$0\$. For example, if we're given a dimension \$4\$ this is what our matrix looks like:
$$
\begin{bmatrix}
0 & 1 & 2 & 3 \\
4 & 5 & 6 & 7 \\
8 & 9 & 10& 11\\
12& 13& 14& 15\\
\end{bmatrix}
$$

Now compute the XOR all of the elements in the upper triangular of the square matrix

0 ^ 1 ^ 2 ^ 3 ^ 4 ^ 5 ^ 6 ^ 8 ^ 9 ^ 12 gives us 10

def computeXOR(dimension):
    XOR = 0
    begin = 0
    for i in range(dimension):
        for j in range(dimension-i):
            XOR ^= begin + (j + i*dimension )
    return XOR

#computeXOR(4) returns 10

I'm trying to think of a faster algorithm to XOR all of the elements in the upper triangular of a square matrix. My current solution is \$O(n^2)\$.

You will need to look at \$O(n^2)\$ elements, therefore there is no algorithm that runs faster than \$O(n^2)\$.

That is, unless you have an explicit formula for the solution which abuses the fact that the elements are all consecutive.

Notice what these XOR to:

cumulative XOR
0 000 000
1 001 001 |
2 010 011 |
3 011 000 |
4 100 100 |
5 101 001
6 110 111
7 111 000

We'll notice a few patterns. The cumulative XOR of all elements \$\lt 2^k\$ for any k is 0.

Here's another, more useful pattern: for any run of \$2^k\$ consecutive elements (e.g. see markers above), all binary digits except the most significant bit will repeat. Therefore we can explicitly compute the XOR of an arbitrarily large sequence \$a \ldots b\$ of length \$2^k\$ in one step (it's all 0s except the most significant digit is b - max(a, largestPowerOf2LessThanB) % 2, I think, where \$\mathrm{largestPowerOf2LessThanB} = 2^{\lfloor\log_2(b)\rfloor}\$).

Therefore we can calculate the sum of any arbitrarily large sequence in roughly \$O(\log(k))\$ steps.

Thus you can make an algorithm with running time \$O(n\log(n))\$ using this explicit formula.

You can maybe make it even faster if you can calculate contiguous blocks of the matrix?

StackExchange Code Review Q#146888, answer score: 5