Neel Mishra
← All Posts
DSA · Bit Manipulation· Part 21 of 32

Fast Walsh-Hadamard Transform

May 2026 · 30 min read

FWT is the bitmask analogue of FFT. Instead of ordinary polynomial convolution, it computes convolutions where the index-combining operation is XOR, OR, or AND. It is an advanced CP tool for problems that ask for counts of pairs or subsets by bitwise result.

XOR Convolution

Given arrays A and B, XOR convolution computes:

C[k] = sum A[i] * B[j] over all i ^ j = k

The transform turns XOR convolution into pointwise multiplication.

void fwht_xor(vector<long long>& a, bool inverse) {
    int n = a.size();
    for (int len = 1; 2 * len <= n; len <<= 1) {
        for (int i = 0; i < n; i += 2 * len) {
            for (int j = 0; j < len; ++j) {
                long long u = a[i + j];
                long long v = a[i + j + len];
                a[i + j] = u + v;
                a[i + j + len] = u - v;
            }
        }
    }
    if (inverse) {
        for (long long& x : a) x /= n;
    }
}

XOR Convolution Template

vector<long long> xor_convolution(vector<long long> a, vector<long long> b) {
    int n = 1;
    while (n < (int)max(a.size(), b.size())) n <<= 1;
    a.resize(n);
    b.resize(n);
    fwht_xor(a, false);
    fwht_xor(b, false);
    for (int i = 0; i < n; ++i) a[i] *= b[i];
    fwht_xor(a, true);
    return a;
}

OR and AND Variants

OR and AND transforms look like zeta transforms. The inverse subtracts what the forward transform added.

void fwt_or(vector<long long>& a, bool inv) {
    int n = a.size();
    for (int len = 1; 2 * len <= n; len <<= 1) {
        for (int i = 0; i < n; i += 2 * len) {
            for (int j = 0; j < len; ++j) {
                if (!inv) a[i + j + len] += a[i + j];
                else      a[i + j + len] -= a[i + j];
            }
        }
    }
}

void fwt_and(vector<long long>& a, bool inv) {
    int n = a.size();
    for (int len = 1; 2 * len <= n; len <<= 1) {
        for (int i = 0; i < n; i += 2 * len) {
            for (int j = 0; j < len; ++j) {
                if (!inv) a[i + j] += a[i + j + len];
                else      a[i + j] -= a[i + j + len];
            }
        }
    }
}

Modular Arithmetic

In modular problems, replace division by n in inverse XOR FWT with multiplication by modular inverse of n. All additions and subtractions should be normalized modulo MOD.

Recognition Guide

Practice Problems