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:

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

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

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;
using ll = long long;

#define endl "\n"

enum class BitOp { XOR, AND, OR };

void FWHT(vector<ll>& a, bool inverse) {
    int n = a.size();
    for (int len = 1; len < n; len <<= 1) {
        for (int i = 0; i < n; i += (len << 1)) {
            for (int j = 0; j < len; j++) {
                ll u = a[i + j];
                ll v = a[i + len + j];
                if (!inverse) {
                    a[i + j] = u + v;
                    a[i + len + j] = u - v;
                }
                else {
                    a[i + j] = (u + v) >> 1;
                    a[i + len + j] = (u - v) >> 1;
                }
            }
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, m;
    cin >> n >> m;
    vector<string> grid(n);
    for (int i = 0; i < n; i++) {
        cin >> grid[i];
    }
    int mask_cnt= 1 << n;
    vector<ll> A(mask_cnt, 0);
    for (int j = 0; j < m; j++) {
        int mask = 0;
        for (int i = 0; i < n; i++) {
            if (grid[i][j] == '1') {
                mask |= (1 << i);
            }
        }
        A[mask]++;
    }
    vector<ll> B(mask_cnt, 0);
    for (int i = 0; i < mask_cnt; i++) {
        int bits = __builtin_popcount(i);
        B[i] = min(bits, n - bits);
    }
    FWHT(A, false);
    FWHT(B, false);
    for (int i = 0; i < mask_cnt; i++) {
        A[i] *= B[i];
    }
    FWHT(A, true);
    ll ans = 1LL * n * m; 
    for (int i = 0; i < mask_cnt; i++) {
        ans = min(ans, A[i]);
    }
    cout << ans << endl;

    return 0;
}

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:

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]$$$:

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:

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:

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$$$:

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:

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

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

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

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.

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.

• Codeforces — 1750E: Bracket Cost
  • Why solve it: A great problem to practice modeling state transitions that can be refactored into fast transform operations.

• SPOJ — MAXMATCH: Maximum Match

  • Why solve it: An excellent introductory problem to practice array alignments and transitions before shifting to full bitwise domains.\

• Codeforces — Yet Another String Matching Problem

  • Why solve it: Mixes string-matching algorithms with optimal polynomial representations, bridging standard FFT foundations with subset combinations.

• CodeChef — Expected Number of Customers
  • Why solve it: Introduces probabilities and expected values over bitwise properties where FWHT accelerates otherwise impossible transitions.
• AtCoder — ABC 212 H: Nim Counting
  • Why solve it: A phenomenal problem to practice FWHT combined with matrix exponentiation (polynomial power) to count winning Nim states.
• Codeforces — 1119H: Triple XOR
  • Why solve it: A legendary 3000-rated problem that pushes the properties of XOR convolution and linearity to their absolute mathematical limits.
• Codeforces — 582E: Boolean Expressions
  • Why solve it: Requires evaluating logical parsing trees using dynamic programming enhanced by AND/OR transforms.
• Codeforces — 1326F2: Wise Men (Hard Version)
  • Why solve it: A masterful challenge blending SOS DP (Sum of Over Subsets), inclusion-exclusion, and advanced bitwise properties.
• Yosupo Library Checker — Bitwise XOR Convolution
  • Why solve it: The pure, unadulterated standard benchmark judge to test your template against optimal global constraints.
• Codeforces — 1494F: Delete The Edges
  • Why solve it: A heavy, graph-oriented problem that can be heavily optimized using SOS DP and submask transitions, serving as an elite training ground for bitwise properties.
• Codeforces — 1521E: Nastia and a Beautiful Matrix
  • Why solve it: Pushes your ability to re-order configuration components linearly under massive bounds, perfect for testing cache-friendly architectures.

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