Learning notes on Fast Bitwise Transform

FWT (Fast Walsh-Hadamard Transform) is a good tool to do fast bitwise convolution. For example, in xor operation, given sequence $A$ and $B$, we can calculate $C$ in $O(n \log n)$ such that $C[i] = \sum_{j \oplus k = i} A[j] \cdot B[k]$.

There are two main properties for the $FWT$ functions for different bitwise operations, where are pretty similar to FFT. The first one is that $FWT(C) = FWT(A) * FWT(B)$, where “$*$” is element-wise multiplication. The second is that there is also $UFWT$ which let us convert the sequence back.

Especially, for “or” operation, $FWT(A)[i] = \sum_{i | j = i} A[j]$, which essentially means the sum over all the subsets for $i$; for “and” operation, $FWT(A)[i] = \sum_{i \land j = i} A[j]$, i.e., sum over supersets.

Related Problems

Frequency Convolution: SRM518 Hard, HDU 5909, HDU 6596
This is the basic application for this transform. Sometimes we can also use fast exponentiation to speed up the same convolution.

Accelerating Brute Force: CF662C
We can see for each way of brute force as a convolution between the frequency and the minimum one we can have for certain number. Thus we can do a convolution for once and get the answer for all.

Making the problem easier: CF800D
If we are asked to solve a problem for some values $x$ and solving for the supersets of $x$ is easier, then we can solve the superset version and transform it back to the exact value version.

Leave a Reply

Your email address will not be published. Required fields are marked *