iv. Bitwise Convolutions

XOR, AND and OR convolutions on arrays of size $2^n$ all follow the same recipe as FFT: transform, multiply pointwise, inverse transform, in $O(n{2}^n)$. Subset (disjoint-union) convolution is in SOS DP.

The three transforms

All three are in-place butterflies on pairs $(u,v)=(a_j,a_{j+len})$:

Convolution	Forward	Inverse
XOR	$(u+v,u-v)$	same, then divide by $2^n$
OR	$(u,u+v)$	$(u,v-u)$
AND	$(u+v,v)$	$(u-v,v)$

template<class T> void fwht(vector<T>& a, bool inv, int type) {   // type: 0 xor, 1 or, 2 and
    int N = a.size();
    for (int len = 1; len < N; len <<= 1)
        for (int i = 0; i < N; i += 2 * len)
            for (int j = i; j < i + len; j++) {
                T u = a[j], v = a[j + len];
                if (type == 0) a[j] = u + v, a[j + len] = u - v;
                else if (type == 1) a[j + len] = inv ? v - u : v + u;
                else a[j] = inv ? u - v : u + v;
            }
    if (type == 0 && inv) { T k = T(1) / T(N); for (auto& x : a) x *= k; }   // modular: multiply by inverse of N
}
// c = a (*) b: fwht(a,0,t); fwht(b,0,t); c[i] = a[i]*b[i]; fwht(c,1,t);

OR and AND are the subset and superset zeta/Möbius transforms. XOR is the Walsh-Hadamard transform — the direct analogue of FFT over $\pm 1$ instead of complex roots of unity. Its coefficients are exactly the Fourier spectrum of a Boolean function over $\mathrm{GF}(2{)}^n$ (the basis of Boolean function analysis and Reed-Muller code decoding), beyond CP but worth knowing where the name comes from:

$\hat{a}(s)={\sum }_t(-1{)}^{\mathrm{popcount}(s\&t)}a(t),H_n^2=2^{n}I.$

Proof: the three butterflies compute the right transform, and the inverses recover the input

XOR (Walsh-Hadamard). By induction on $n$: for $n=0$ the transform is the identity, matching $H_0=[1]$. Splitting a size-$2^n$ array into first/second halves of size $2^{n-1}$, running the inductive transform on each half independently (this is exactly what the level-by-level loop does: at level $\log$-size $2^{n-1}$ the recursion has already combined everything below that size within each half) gives $H_{n-1}\cdot a_{\text{first}}$ and $H_{n-1}\cdot a_{\text{second}}$; the final butterfly $(u,v)\mapsto (u+v,u-v)$ on corresponding entries is exactly the block matrix H_n=\begin{psmallmatrix}H_{n-1}&H_{n-1}\\H_{n-1}&-H_{n-1}\end{psmallmatrix} applied to the concatenation, by direct expansion of the block product. So the butterfly computes $H_n\cdot a$ for all $n$. Since $H_n$ is symmetric with $H_n^2=2^{n}I$ (each diagonal entry of $H_n^2$ sums ${\sum }_{t}1=2^n$, and each off-diagonal entry is ${\sum }_t(-1{)}^{\mathrm{popcount}((s\oplus s^{\prime })\&t)}$ which is $0$ by pairing $t\leftrightarrow t\oplus e$ for any bit $e$ where $s,s^{\prime }$ differ), running the same butterfly again and dividing by $2^n$ recovers $a$ exactly, so transform-multiply-inverse computes $H_n^{-1}\mathrm{diag}(H_{n}a)H_{n}b$, and since $\widehat{a\oplus b\text{-conv}}=\hat{a}\cdot \hat{b}$ pointwise (the defining property of the XOR character $(-1{)}^{\mathrm{popcount}(s\&t)}$ being multiplicative under XOR convolution), this is exactly the XOR convolution of $a,b$. OR/AND. The OR butterfly $(u,v)\mapsto (u,u+v)$ applied bit-by-bit across all $\log N$ levels is literally the subset-zeta dimension sweep from SOS DP (there proved to compute $\hat{a}(S)={\sum }_{T\subseteq S}a(T)$) — the butterfly’s pairing of indices differing in bit $i$ within blocks of size $2\cdot 2^i$ is the same pairing the sweep uses, just phrased with explicit len doubling instead of an explicit bit index. Its stated inverse $(u,v)\mapsto (u,v-u)$ undoes each addition exactly, recovering $a$. The pointwise product of two subset-zeta transforms, Möbius-inverted, is the OR convolution by the same argument as the zeta/Möbius proof in SOS DP (restricted to $k=0$, i.e. no popcount ranking, so overlaps are allowed — matching the OR convolution’s definition, which permits $A\cap B\ne \varnothing$). The AND case is the mirror image (superset sums) by symmetry under bit complementation. $■$

Tested: all three butterflies (XOR/OR/AND), each transform→pointwise-multiply→inverse pipeline, checked against the direct $O(N^2)$ definition of the respective convolution for $n$ up to 6, random double arrays, matching to $10^{-6}$.

Using the transform structure

The transform of a single “indicator” ${\delta }_x$ is $\pm 1$ everywhere: ${\hat{\delta }}_x(s)=(-1{)}^{|s\&x|}$. So products of many sparse factors can be computed in the transform domain without convolving them one by one.

Count subsets with XOR $=x$, or choose one element from each of $n$ groups: for “pick any subset of $a_1..a_m$”, the product is ${\prod }_i({\delta }_0+{\delta }_{a_i})$. In the transform domain each factor is $1+(-1{)}^{|s\&a_i|}\in \{0,2\}$. So $\hat{P}(s)=2^m$ if every $a_i$ has even overlap with $s$, else 0. (The rank of an XOR basis gives the same answer: $2^{m-r}$ subsets per reachable value.)

Product of factors $({\delta }_0\cdot c_i+{\delta }_{a_i}\cdot d_i)$ where each transform takes only two values $c_i+d_i$ or $c_i-d_i$: for each $s$, count how many factors take the “minus” value. Let $k(s)$ be that count; then $\hat{P}(s)=\prod$ over the “plus” factors times the “minus” factors. Counting $k(s)$ for all $s$ needs one more transform of the sum of the indicators: ${\sum }_i{\hat{\delta }}_{a_i}(s)=(m-k)-k$. This is the classic trick for “each of $m$ triples, choose one value, count XOR outcomes” in $O(n{2}^n)$ (CF 1119H “Triple”): with three values per group, solve a small linear system for the number of groups in each sign pattern.

Repeated self-convolution: $a^{\ast k}$ is pointwise $\hat{a}(s{)}^k$, so “XOR of $k$ independent choices” costs one transform plus fast powers.

Rank and linear algebra: the support of the transform of the indicator of a linear subspace $V$ is its orthogonal complement $V^{\perp }$. That links XOR transforms to XOR bases (XOR Basis).

Variants

• Modular arithmetic: the XOR inverse divides by $2^n$; multiply by its modular inverse (needs an odd modulus).
• Floating point: fine for probabilities. Use double and divide by $N$ at the end.
• Base-$k$ “XOR” (digit-wise addition mod $k$): use the $k$-point DFT on each digit (roots of unity mod $p$ when $k\mid p-1$, or an extension ring). For $k=3$ the transform uses $\omega$ with ${\omega }^2+\omega +1=0$.
• Max-plus “OR convolution” (${\max }_{A\cup B=S}f(A)+g(B)$): no fast transform in general. If $f$ is monotone, zeta with max then split as needed; otherwise subset enumeration in $O(3^n)$.
• GCD and LCM convolutions on $[1,N]$: the same idea on the divisor lattice. “Sum over multiples” (zeta) and Möbius over divisors give ${\sum }_{\gcd (i,j)=k}{a}_i{b}_j$ in $O(N\log \log N)$ with a prime-by-prime sweep (Möbius).

Uses

Problem	Convolution
number of pairs with $a_i\oplus a_j=x$ for every $x$	XOR self-convolution of frequencies
Nim: probability the XOR of random piles is 0	XOR power of the pile distribution
count pairs with $a_i\mid a_j=x$	OR convolution
expected value of AND of random picks	AND convolution
”choose one of three values in each group, count XOR results”	transform-domain counting (above)
game sums: distribution of Grundy XOR	XOR convolution