Recently I was trying to solve the following problem: 102441E - Очень простая сумма.
In process of solving it, I realised that I need to use xor convolution and just copied FWHT code somewhere from the internet. My solution passed, but I wanted to know how does it work, so started searching info on FWHT and xor convolution.
After some time of going through endless blogs talking about weird matrices and other difficult stuff, I decided to reinvent everything on my own, as I always do. Here I will describe a simple algorithmic way to look at xor convolution, I hope that it doesn't contain any crucial mistakes and will be useful for you.
The Algorithm
Let the size of the arrays be $$$2^n$$$, we want to calculate
for all $$$0\le i\le 2^n - 1$$$.
If we look at halves of the arrays separately, first half consists of indices with $$$n$$$-th bit set to zero, and the second consists of indices with $$$n$$$-th bit set to one, so the sum becomes
where $$$X0$$$ is the first half of $$$X$$$ and $$$X1$$$ is the second.
Let's take a look at the xor convolution of $$$A0+A1$$$ and $$$B0+B1$$$: