Bitwise XOR Convolution
(convolution/xor_convolution.hpp)

• View this file on GitHub
• Last update: 2024-01-08 17:31:43+09:00
• Include: #include "convolution/xor_convolution.hpp"

Depends on

• Fast Walsh-Hadamard Transform (convolution/walsh_hadamard_transform.hpp)

Verified with

• test/yosupo/bitwise_xor_convolution.test.cpp

Code

#pragma once
#include <bit>
#include <vector>

#include "walsh_hadamard_transform.hpp"

/**
 * @brief Bitwise XOR Convolution
 */

template <typename T>
std::vector<T> xor_convolution(std::vector<T> a, std::vector<T> b) {
    const int n = std::bit_ceil(std::max(a.size(), b.size()));
    a.resize(n);
    b.resize(n);
    fwht(a);
    fwht(b);
    for (int i = 0; i < n; ++i) a[i] *= b[i];
    ifwht(a);
    return a;
}

#line 2 "convolution/xor_convolution.hpp"
#include <bit>
#include <vector>

#line 3 "convolution/walsh_hadamard_transform.hpp"
#include <cassert>
#line 5 "convolution/walsh_hadamard_transform.hpp"

template <typename T>
void fwht(std::vector<T>& a) {
    assert(std::has_single_bit(a.size()));
    const int n = a.size();
    for (int h = 1; h < n; h <<= 1) {
        for (int i = 0; i < n; i += h << 1) {
            for (int j = i; j < i + h; ++j) {
                T x = a[j], y = a[j | h];
                a[j] = x + y;
                a[j | h] = x - y;
            }
        }
    }
}

template <typename T>
void ifwht(std::vector<T>& a) {
    assert(std::has_single_bit(a.size()));
    const int n = a.size();
    const T inv2 = T(1) / 2;
    for (int h = 1; h < n; h <<= 1) {
        for (int i = 0; i < n; i += h << 1) {
            for (int j = i; j < i + h; ++j) {
                T x = a[j], y = a[j | h];
                a[j] = (x + y) * inv2;
                a[j | h] = (x - y) * inv2;
            }
        }
    }
}
#line 6 "convolution/xor_convolution.hpp"

/**
 * @brief Bitwise XOR Convolution
 */

template <typename T>
std::vector<T> xor_convolution(std::vector<T> a, std::vector<T> b) {
    const int n = std::bit_ceil(std::max(a.size(), b.size()));
    a.resize(n);
    b.resize(n);
    fwht(a);
    fwht(b);
    for (int i = 0; i < n; ++i) a[i] *= b[i];
    ifwht(a);
    return a;
}

Back to top page