一、算法概述
快速沃尔什变换（Fast Walsh-Hadamard Transform，简称 FWT）是一种基于”分治 + 蝶形运算”的快速变换算法，主要用于加速 位运算卷积。它可以在 O(n log n) 时间内完成两个长度为 n 的序列的卷积，前提是这个卷积是用”按位与（AND）”、”按位或（OR）”或”按位异或（XOR）”定义的指数生成函数意义上的乘法。这与传统的多项式卷积（NTT/FFT）形式上完全类似，但底层”基函数”从单位根换成了二进制下的沃尔什-哈达玛矩阵，因此称为 FWT。
FWT 的核心应用包括：
1. 位运算卷积：例如求解”对所有 (i & j) = k 的对求 A[i] * B[j]”；
2. 子集和 / 超集和：在 O(n log n) 时间内把一个 2^n 大小的数组变换为子集和或超集和数组；
3. 子集卷积：对 (i & j) = 0 的约束下的卷积，可以用 FWT 结合拆分技巧实现 O(2^n * n²)；
4. 博弈计数：在 Sprague-Grundy 定理下用 FWT 加速异或卷积。
本文将系统讲解 FWT 的原理，并给出 AND、OR、XOR 三种卷积的完整 Java 实现，以及子集卷积的扩展实现。
二、算法原理
2.1 沃尔什-哈达玛矩阵
哈达玛矩阵 H_n 是 2^n × 2^n 的矩阵，满足 H_n * H_n^T = 2^n * I，并且它的递归构造为：
H_0 = [1]
H_n = [H_{n-1} H_{n-1}]
[H_{n-1} -H_{n-1}]
这种矩阵把”按位异或卷积”映射为”按位乘法”（类似 FFT 把多项式乘积映射为点值乘积）。对于 AND / OR 卷积，矩阵略有不同（不带正负号，但元素是 0/1）。
2.2 XOR 卷积的 FWT
定义两个长度为 2^n 的序列 A、B，XOR 卷积 C 的定义为：
C[k] = sum_{i XOR j = k} A[i] * B[j]
直接按定义计算是 O(n²)。FWT 的核心思想是引入变换 fwt_xor(A)，使得：
fwt_xor(C) = fwt_xor(A) pointwise-multiply fwt_xor(B)
而 fwt_xor 本身可以在 O(n log n) 时间内计算。它的递归公式为：设 A0 = A[0..mid-1]，A1 = A[mid..n-1]（n 为偶数），则：
fwt(A0') = U1 + U2
fwt(A1') = U1 - U2
其中 U1 = fwt(A0)，U2 = fwt(A1)，长度均为 n/2。逆变换 ifwt 用类似公式，但最后要除以 2。
代码上一般写成：
for (int len = 1; len < n; len <<= 1) {
for (int i = 0; i < n; i += len << 1) {
for (int j = 0; j < len; j++) {
int u = a[i + j];
int v = a[i + j + len];
a[i + j] = u + v;
a[i + j + len] = u - v;
}
}
}
2.3 OR 卷积的 FWT
OR 卷积的定义为：
C[k] = sum_{i OR j = k} A[i] * B[j]
这里”等于”是按位或。FWT 的构造方法是把 A 变换为”超集和” F[k] = sum_{i ⊆ k} A[i]（这里的 ⊆ 是”按位 i 是 k 的子集”）。变换后的点值乘积，再逆变换回原空间，就得到了 OR 卷积。
变换公式：
for (int len = 1; len < n; len <<= 1) {
for (int i = 0; i < n; i += len << 1) {
for (int j = 0; j < len; j++) {
a[i + j + len] += a[i + j];
}
}
}
逆变换把 += 改成 -=。
2.4 AND 卷积的 FWT
AND 卷积的定义为：
C[k] = sum_{i AND j = k} A[i] * B[j]
构造思路与 OR 卷积类似，但方向相反——把 A 变换为”子集和” F[k] = sum_{i ⊇ k} A[i]。代码与 OR 卷积对称，把 += a[i+j] 改成 += a[i+j+len]。
2.5 子集卷积
子集卷积的定义为：
C[k] = sum_{i AND j = 0, i OR j = k} A[i] * B[j]
也就是”在 i 和 j 没有公共 1 位的前提下，i OR j = k 的所有 (i, j) 对”。这一约束不能用普通 FWT 直接处理。常用技巧是：
1. 拆分计数维度：设 popcount(i) = p 表示 i 中 1 的个数，把 A[i] 拆分为 A'[i][p]；同理拆 B；
2. 逐 popcount 做 FWT：对每个 p（0..n），先做”按位变换”，得到 FA'[i][p]；
3. 点乘累加：对每个 k 和每个 p（p0 + p1 = popcount(k)），把 FA'[k][p0] 与 FB'[k][p1] 的乘积累加到 FC'[k][p0+p1]；
4. 逆变换：对每个 popcount 维度做逆 FWT，得到 C'[k][popcount(k)]，去掉其他维即可。整个过程复杂度 O(n² · 2^n)。
三、Java 实现
下面给出一个完整的、可直接运行的 Java 实现。包含：
XorFWT：XOR 卷积；OrFWT：OR 卷积；AndFWT：AND 卷积；SubsetConvolution：子集卷积；main：每个算法都给出 demo 用例。
import java.util.Arrays;
/**
* 快速沃尔什变换（FWT）
*
* 支持：
* 1. XOR 卷积
* 2. OR 卷积
* 3. AND 卷积
* 4. 子集卷积（Subset Convolution）
*
* 复杂度：O(n log n) 每卷积，子集卷积 O(n² * 2^n)
*
* 数组长度必须为 2 的幂。
*/
public class FastWalshHadamard {
// ============================================================
// 1) XOR 卷积
// C[k] = sum_{i XOR j = k} A[i] * B[j]
// ============================================================
public static double[] xorConvolution(double[] a, double[] b) {
int n = Math.max(a.length, b.length);
n = Integer.highestOneBit(n - 1) << 1; // 向上取整为 2 的幂
double[] A = Arrays.copyOf(a, n);
double[] B = Arrays.copyOf(b, n);
fwtXor(A);
fwtXor(B);
for (int i = 0; i < n; i++) {
A[i] *= B[i];
}
ifwtXor(A);
return A;
}
private static void fwtXor(double[] a) {
int n = a.length;
for (int len = 1; len < n; len <<= 1) {
for (int i = 0; i < n; i += len << 1) {
for (int j = 0; j < len; j++) {
double u = a[i + j];
double v = a[i + j + len];
a[i + j] = u + v;
a[i + j + len] = u - v;
}
}
}
}
private static void ifwtXor(double[] a) {
int n = a.length;
for (int len = 1; len < n; len <<= 1) {
for (int i = 0; i < n; i += len << 1) {
for (int j = 0; j < len; j++) {
double u = a[i + j];
double v = a[i + j + len];
a[i + j] = (u + v) / 2;
a[i + j + len] = (u - v) / 2;
}
}
}
}
// ============================================================
// 2) OR 卷积
// C[k] = sum_{i OR j = k} A[i] * B[j]
// ============================================================
public static double[] orConvolution(double[] a, double[] b) {
int n = Math.max(a.length, b.length);
n = Integer.highestOneBit(n - 1) << 1;
double[] A = Arrays.copyOf(a, n);
double[] B = Arrays.copyOf(b, n);
fwtOr(A);
fwtOr(B);
for (int i = 0; i < n; i++) {
A[i] *= B[i];
}
ifwtOr(A);
return A;
}
private static void fwtOr(double[] a) {
int n = a.length;
for (int len = 1; len < n; len <<= 1) {
for (int i = 0; i < n; i += len << 1) {
for (int j = 0; j < len; j++) {
a[i + j + len] += a[i + j];
}
}
}
}
private static void ifwtOr(double[] a) {
int n = a.length;
for (int len = 1; len < n; len <<= 1) {
for (int i = 0; i < n; i += len << 1) {
for (int j = 0; j < len; j++) {
a[i + j + len] -= a[i + j];
}
}
}
}
// ============================================================
// 3) AND 卷积
// C[k] = sum_{i AND j = k} A[i] * B[j]
// ============================================================
public static double[] andConvolution(double[] a, double[] b) {
int n = Math.max(a.length, b.length);
n = Integer.highestOneBit(n - 1) << 1;
double[] A = Arrays.copyOf(a, n);
double[] B = Arrays.copyOf(b, n);
fwtAnd(A);
fwtAnd(B);
for (int i = 0; i < n; i++) {
A[i] *= B[i];
}
ifwtAnd(A);
return A;
}
private static void fwtAnd(double[] a) {
int n = a.length;
for (int len = 1; len < n; len <<= 1) {
for (int i = 0; i < n; i += len << 1) {
for (int j = 0; j < len; j++) {
a[i + j] += a[i + j + len];
}
}
}
}
private static void ifwtAnd(double[] a) {
int n = a.length;
for (int len = 1; len < n; len <<= 1) {
for (int i = 0; i < n; i += len << 1) {
for (int j = 0; j < len; j++) {
a[i + j] -= a[i + j + len];
}
}
}
}
// ============================================================
// 4) 子集卷积
// C[k] = sum_{i AND j = 0, i OR j = k} A[i] * B[j]
// 要求 A、B 长度 n = 2^m，且 m 比较小（一般 m ≤ 18）
// ============================================================
/**
* 计算 popcount（1 的个数）
*/
private static int popcount(int x) {
return Integer.bitCount(x);
}
public static double[] subsetConvolution(double[] a, double[] b) {
int n = Math.max(a.length, b.length);
int m = Integer.numberOfTrailingZeros(n);
if ((1 << m) != n) {
throw new IllegalArgumentException("数组长度必须为 2 的幂");
}
// 1) 按 popcount 拆分：F[i][p] = A[i]（如果 popcount(i) = p）否则 0
double[][] FA = new double[n][m + 1];
double[][] FB = new double[n][m + 1];
for (int i = 0; i < n; i++) {
int p = popcount(i);
if (p <= m) {
FA[i][p] = a[i];
FB[i][p] = b[i];
}
}
// 2) 对每个 popcount 维度做 OR-FWT（变成超集和）
for (int p = 0; p <= m; p++) {
// 对 FA[*][p] 做 OR-FWT
double[] arr = new double[n];
for (int i = 0; i < n; i++) arr[i] = FA[i][p];
fwtOr(arr);
for (int i = 0; i < n; i++) FA[i][p] = arr[i];
arr = new double[n];
for (int i = 0; i < n; i++) arr[i] = FB[i][p];
fwtOr(arr);
for (int i = 0; i < n; i++) FB[i][p] = arr[i];
}
// 3) 点乘累加：FC[i][p0+p1] += FA[i][p0] * FB[i][p1]
double[][] FC = new double[n][m + 1];
for (int i = 0; i < n; i++) {
for (int p0 = 0; p0 <= m; p0++) {
if (FA[i][p0] == 0) continue;
for (int p1 = 0; p1 + p0 <= m; p1++) {
FC[i][p0 + p1] += FA[i][p0] * FB[i][p1];
}
}
}
// 4) 对每个 popcount 维度做逆 OR-FWT
for (int p = 0; p <= m; p++) {
double[] arr = new double[n];
for (int i = 0; i < n; i++) arr[i] = FC[i][p];
ifwtOr(arr);
for (int i = 0; i < n; i++) FC[i][p] = arr[i];
}
// 5) 合并：结果 C[i] = FC[i][popcount(i)]
double[] C = new double[n];
for (int i = 0; i < n; i++) {
C[i] = FC[i][popcount(i)];
}
return C;
}
// ================== 演示入口 ==================
public static void main(String[] args) {
// XOR 卷积示例
double[] A = {1, 1, 1, 1}; // 长度 4
double[] B = {1, 1, 1, 1};
double[] C = xorConvolution(A, B);
System.out.println("XOR 卷积结果（长度 " + C.length + "）：");
System.out.println(Arrays.toString(C));
// 期望：[4, 0, 0, 0]，因为 i XOR j 在每个 k 上的分布数相同
// OR 卷积示例
double[] OR1 = {1, 1, 1, 1};
double[] OR2 = {1, 1, 1, 1};
double[] OR_C = orConvolution(OR1, OR2);
System.out.println("OR 卷积结果：");
System.out.println(Arrays.toString(OR_C));
// 期望：[1, 2, 2, 4]
// AND 卷积示例
double[] AND1 = {1, 1, 1, 1};
double[] AND2 = {1, 1, 1, 1};
double[] AND_C = andConvolution(AND1, AND2);
System.out.println("AND 卷积结果：");
System.out.println(Arrays.toString(AND_C));
// 期望：[4, 2, 2, 1]
// 子集卷积示例
double[] S1 = {1, 0, 0, 0};
double[] S2 = {0, 1, 0, 0};
double[] SC = subsetConvolution(S1, S2);
System.out.println("子集卷积结果：");
System.out.println(Arrays.toString(SC));
// 期望：C[3] = 1（i=1, j=2 时 i OR j = 3 且 i AND j = 0），其它为 0
}
}
3.1 代码解读
fwtXor/ifwtXor：XOR 卷积的蝶形变换与逆变换。注意逆变换要除以 2 才能恢复。fwtOr/ifwtOr：OR 卷积的”超集和”形式，逆变换用减法。fwtAnd/ifwtAnd：AND 卷积的”子集和”形式，与 OR 对称。subsetConvolution：实现子集卷积的核心技巧——按 popcount 维度拆分，分别做 OR-FWT、点乘、逆变换。这个 5 步流程是处理”AND 不相交约束”的通用套路。
四、复杂度分析
| 卷积类型 | 时间复杂度 | 空间复杂度 |
|---|---|---|
| XOR | O(n log n) | O(n) |
| OR | O(n log n) | O(n) |
| AND | O(n log n) | O(n) |
| 子集 | O(n² · 2^n) | O(n² · 2^n) |
其中 n = 2^m，m 是位数（一般 ≤ 20）。
注意点：
– 数组长度必须为 2 的幂，不足时填零补齐；
– 使用 double 类型，长度 2^20 = 1M 时大约 8 MB；如果用 long 加 NTT 风格，可以达到精确计算；
– XOR 卷积中，fwt 与 ifwt 的系数比是 1:1/2，需要注意。
五、应用场景
5.1 位运算卷积
FWT 最直接的应用就是位运算卷积。在处理”按位与/或/异或约束”的问题时，FWT 几乎是必备工具。例如：
– 给定一个集合 S，求所有”按位与为 0 的子集对”的数量；
– 给定两个长度 2^n 的数组，求它们在异或意义下的卷积。
5.2 博弈论（SG 函数）
在 Sprague-Grundy 定理下，两个子游戏合并的 SG 值就是两个子游戏的 SG 值的异或。所以”在异或结果为 0 的情况下，先手必败”这类问题本质就是用 FWT 加速统计。
5.3 字符串匹配
把字符映射成 0/1 位后，可以用 FWT 做”任意位置子串”的最长公共子序列计数。这种技巧在生物信息学中常见。
5.4 集合计数
“集合族 A 与集合族 B 中元素个数为 k 的交集的元素数”——这是经典的”交集卷积”，可以用 FWT + 位运算解决。
5.5 注意事项
- 数组长度补齐：FWT 要求长度为 2 的幂，输入数组可能不是，必须补齐；
- 整数 vs 浮点：XOR 卷积用整数（保留 ±）即可；但 OR/AND 因为只有加法，必须用浮点（防止溢出）；
- 子集卷积的复杂度：O(n²·2^n) 在 n=18 时已经较慢（n=18 → 18² · 2^18 ≈ 85M），n=20 就要小心常数；
- 回代精度：XOR 逆变换要除以 2^n，建议使用 long 类型避免精度丢失。
六、总结
FWT 是处理位运算卷积的”瑞士军刀”，它在 O(n log n) 时间内完成本来 O(n²) 的卷积。它的核心思想是借助于沃尔什-哈达玛矩阵将”按位运算的卷积”转换为”点值乘法”，这一点与 FFT/NTT 的设计哲学完全一致。
本文给出了 AND、OR、XOR 三种卷积以及子集卷积的完整 Java 实现，并详细解释了每一步的几何含义。希望读者通过本文能够：
1. 理解 FWT 的蝶形运算原理，包括正逆变换的几何意义；
2. 能够背诵三种变换的代码，因为它们的代码非常简短；
3. 理解子集卷积的拆分维度技巧，这是处理更复杂位运算问题的关键；
4. 在竞赛中识别 FWT 适用的问题，并能在 5 分钟内完成实现。
掌握 FWT 后，很多看似复杂的位运算计数题都能在 O(n log n) 内轻松解决。配合 NTT、莫队等高级算法，你可以处理更广泛的问题类型。祝学习愉快！
