Fast Walsh-Hadamard Transform

Правка en1, от _Overoptimizer_, 2026-10-12 14:36:33

Hello community! So I guess most people here do not know about Fast Walsh-Hadamard Transform (FWHT), which is a beautiful algorithm. Its most famous feat is solving bitwise convolutions in O (N log N) time, a problem that would otherwise trap you in an O(N²) brute-force nightmare. If you've ever used Fast Fourier Transform (FFT) to multiply polynomials, FWHT is its hardcore, bit-manipulating cousin that operates directly in the realm of XOR,AND,and OR operations. Today, we are going to dive straight to the bottom of the ocean—exploring the stunning mathematics behind FWHT and implementing a cache-friendly, ultra-optimized C++ template that works at the transistor level.

here is the code which is O (N ^ 2) time complexity 

for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
        C[i ^ j] += A[i] * B[j]; 
    }
}

For the XOR operation, the transformation relies on the Hadamard Matrix ($$$H_n$$$). It is defined recursively as:

$$$H_0 = \begin{pmatrix} 1 \end{pmatrix}$$$
$$$H_n = \begin{pmatrix} H_{n-1} & H_{n-1} \\ H_{n-1} & -H_{n-1} \end{pmatrix}$$$

For example, a $$$2 \times 2$$$ Hadamard matrix looks like this:

$$$H_1 = \begin{pmatrix} 1 & 1 \\ 1 & -1 \end{pmatrix}$$$

Why this specific matrix? Because its individual elements perfectly reflect the dot product of bits at the hardware level:

This innate symmetry fits the bitwise nature of XOR perfectly.

so here is our optimize code which is O (N log N)

#include <vector>
#include <iostream>

enum class BitOp { XOR, AND, OR };

// In-place FWHT: O(N log N) time and O(1) auxiliary memory
void FWHT(std::vector<long long>& a, BitOp op, bool inverse) {
    int n = a.size();
    
    // Linear iterative loops designed to maximize CPU pipeline efficiency
    for (int len = 1; len < n; len <<= 1) {
        for (int i = 0; i < n; i += (len << 1)) {
            for (int j = 0; j < len; j++) {
                long long u = a[i + j];
                long long v = a[i + len + j];
                
                if (op == BitOp::XOR) {
                    if (!inverse) {
                        a[i + j] = u + v;
                        a[i + len + j] = u - v;
                    } else {
                        // Inverse XOR requires dividing by 2.
                        // Bit shifting (>> 1) takes exactly 1 clock cycle on standard CPUs!
                        a[i + j] = (u + v) >> 1;
                        a[i + len + j] = (u - v) >> 1;
                    }
                } 
                else if (op == BitOp::OR) {
                    a[i + len + j] = !inverse ? (u + v) : (v - u);
                } 
                else if (op == BitOp::AND) {
                    a[i + j] = !inverse ? (u + v) : (u - v);
                }
            }
        }
    }
}

// Master function to execute the full Bitwise Convolution
std::vector<long long> bitwise_convolution(std::vector<long long> A, std::vector<long long> B, BitOp op) {
    FWHT(A, op, false);
    FWHT(B, op, false);
    
    for (size_t i = 0; i < A.size(); i++) {
        A[i] *= B[i];
    }
    
    FWHT(A, op, true); // Inverse transform back to original domain
    return A;
}

The reason that is faster than previous version is because of

Bitwise Shift Arithmetic (len <<= 1): We completely bypass slow assembly division or multiplication instructions by shifting bits directly left or right. It is the cheapest hardware instruction execution possible.

Spatial Locality (Cache Friendliness): The nested loops process indices linearly. The CPU's Hardware Prefetcher effortlessly predicts this stream, pulling data from RAM straight into the L1/L2 cache lines before the code even requests them. Cache misses drop to nearly zero.

OK, so we saw the template itself let's solve one problem:

Binary Table (https://codeforces.me/contest/662/problem/C) time limit per test

6 seconds

memory limit per test

256 megabytes You are given a table consisting of n rows and m columns. Each cell of the table contains either 0 or 1. In one move, you are allowed to pick any row or any column and invert all values, that is, replace 0 by 1 and vice versa.

What is the minimum number of cells with value 1 you can get after applying some number of operations?

Input The first line of the input contains two integers n and m (1 ≤ n ≤ 20, 1 ≤ m ≤ 100 000) — the number of rows and the number of columns, respectively.

Then n lines follows with the descriptions of the rows. Each line has length m and contains only digits '0' and '1'.

Output Output a single integer — the minimum possible number of ones you can get after applying some sequence of operations.

Example

InputCopy

3 4

0110

1010

0111

OutputCopy

2

here is my code

To completely understand why this works, let's break down the logic step-by-step from raw formulas to the clean XOR convolution.

Let $$$R$$$ be the bitmask representing our choices of row flips. If the $$$i$$$-th bit of $$$R$$$ is $$$1$$$, it means we flip the $$$i$$$-th row.

If we apply the row flips $$$R$$$, any column whose initial configuration had a bitmask $$$mask$$$ will transform into a new configuration:

$$$\text{new\_mask} = mask \oplus R$$$

For this column, we want to minimize the number of ones. We can choose to either flip this column entirely or leave it as it is.

  • If we do nothing, the number of 1s is: popcount(mask XOR R)
  • If we flip the column, the number of 1s becomes: N - popcount(mask XOR R)

To get the absolute minimum, we define a precomputed function $$$B[x]$$$:

$$$B[x] = \min(\text{popcount}(x), N - \text{popcount}(x))$$$

Thus, the number of $$$1$$$s contributed by a column with the shape $$$mask \oplus R$$$ is exactly $$$B[mask \oplus R]$$$.

Let $$$A[mask]$$$ be the frequency array indicating how many columns in the given initial table have the exact bitmask $$$mask$$$.

For a fixed row flip choice $$$R$$$, the total number of $$$1$$$s in the entire table, $$$Total(R)$$$, is the sum of costs over all possible column masks:

$$$Total(R) = \sum_{mask = 0}^{2^N - 1} A[mask] \cdot B[mask \oplus R]$$$

If we compute this directly for all $$$2^N$$$ possible row flip masks $$$R$$$, each taking $$$O(2^N)$$$ summation steps, the overall runtime becomes $$$O(2^N \cdot 2^N) = O(4^N)$$$. With $$$N = 20$$$, $$$4^{20} \approx 10^{12}$$$, which is too slow. We must optimize this expression.

Let's introduce a new variable, $$$target$$$, to track the state after the bitwise operation. We define:

$$$target = mask \oplus R$$$

Using the foundational properties of the XOR ((\oplus)) operation, we know that if $$$target = mask \oplus R$$$, then we can XOR both sides by $$$R$$$ to isolate $$$mask$$$:

$$$mask = target \oplus R$$$

Now, let's substitute $$$mask$$$ inside our $$$Total(R)$$$ equation. The summation domain remains exactly the same ($$$0$$$ to $$$2^N - 1$$$) because XOR is a bijective permutation over the set of masks:

$$$Total(R) = \sum_{target = 0}^{2^N - 1} A[target \oplus R] \cdot B[target]$$$

Because XOR is commutative ($$$target \oplus R = R \oplus target$$$), we can rewrite it as:

$$$Total(R) = \sum_{target = 0}^{2^N - 1} A[R \oplus target] \cdot B[target]$$$

Look at the mathematical definition of a standard Bitwise XOR Convolution between two arrays $$$X$$$ and $$$Y$$$:

$$$Z[k] = \sum_{i \oplus j = k} X[i] \cdot Y[j]$$$

By utilizing the properties of the Walsh-Hadamard Transform, this convolution can be computed instantaneously in the transformed frequency domain:

$$$\text{FWHT}(Z) = \text{FWHT}(X) \cdot \text{FWHT}(Y)$$$

Our equation $$$Total(R) = \sum A[R \oplus target] \cdot B[target]$$$ fits this pattern perfectly! * Array $$$A$$$ acts as our first polynomial. * Array $$$B$$$ acts as our second polynomial. * The index $$$R$$$ acts as the target convolution bit state $$$k$$$.

By applying the forward $$$\text{FWHT}$$$ to both frequency spectrum matrices $$$A$$$ and $$$B$$$, performing a linear $$$O(2^N)$$$ pointwise dot-product multiplication, and applying the Inverse $$$\text{FWHT}$$$ back, we obtain the $$$Total(R)$$$ answers for all $$$2^N$$$ row configurations simultaneously.

$$$\text{Final Complexity:} \quad O(N \cdot 2^N)$$$

so our topic's end is here, here is more problems for your practise and grow in this technique

  • Codeforces — 914G: Sum the Elements

  • Why solve it: This is the ultimate test for bitwise convolutions. It requires you to simultaneously combine AND, OR, and XOR convolutions alongside Fibonacci numbers in a single problem.

and do not forget to read this too :) -> (https://cp-algorithms.com/algebra/fft.html)

Теги fwht

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en2 Английский _Overoptimizer_ 2026-10-12 14:37:37 7 (published)
en1 Английский _Overoptimizer_ 2026-10-12 14:36:33 12981 Initial revision (saved to drafts)