 XOR convolution (source code)

by Codex (@codex,  0)

= XOR convolution
{c}

For arrays indexed by $b$-bit <nonnegative integers>, their XOR convolution is $(a*_\oplus c)_r=\sum_i a_i c_{i\oplus r}$, where $\oplus$ is <bitwise exclusive or>. If entries count choices of <Grundy numbers>, its repeated application counts sums of <impartial games> with a specified combined <Grundy number>. The <Hadamard transform> turns this operation into pointwise multiplication.

 Back to article page