Bitwise Xor Convolution
(src/algebra/convolution/bitxor.hpp)

• View this file on GitHub
• Last update: 2021-05-31 22:43:54+09:00
• Include: #include "src/algebra/convolution/bitxor.hpp"

Verified with

• test/library-checker/bitwise_xor_convolution.test.cpp

Code

#pragma once

/**
 * @file bitxor.hpp
 * @brief Bitwise Xor Convolution
 * @date 2021-01-08
 */

#include <iterator>

#include "lib/bit"

namespace workspace {

template <class A> A bitwise_fft(A f) {
  size_t len = std::__bit_floor(std::size(f));
  for (size_t p = 1; p < len; p <<= 1) {
    for (size_t i = 0; i < len; i += p << 1) {
      for (size_t j = 0; j < p; ++j) {
        auto t = f[i + j + p];
        f[i + j + p] = f[i + j] - t;
        f[i + j] += t;
      }
    }
  }
  return f;
}

template <class A> A bitwise_ifft(A f) {
  size_t len = std::__bit_floor(std::size(f));
  for (size_t p = len; p != 1; p >>= 1) {
    for (size_t i = 0; i < len; i += p) {
      for (size_t j = 0; j << 1 < p; ++j) {
        auto t = f[i + j + (p >> 1)];
        f[i + j + (p >> 1)] = (f[i + j] - t) / 2;
        (f[i + j] += t) /= 2;
      }
    }
  }
  return f;
}

template <class A> A bitxor_conv(A f, A g) {
  f = bitwise_fft(f);
  g = bitwise_fft(g);
  for (size_t i = 0; i != std::size(f); ++i) f[i] *= g[i];
  f = bitwise_ifft(f);
  return f;
}

}  // namespace workspace

#line 2 "src/algebra/convolution/bitxor.hpp"

/**
 * @file bitxor.hpp
 * @brief Bitwise Xor Convolution
 * @date 2021-01-08
 */

#include <iterator>

#line 2 "lib/bit"

#if __cplusplus > 201703L

#include <bit>

#elif __cplusplus > 201402L

#ifndef _GLIBCXX_BIT
#define _GLIBCXX_BIT 1

#include <limits>
#include <type_traits>

namespace std {

template <typename _Tp> constexpr int __countl_zero(_Tp __x) noexcept {
  constexpr auto _Nd = numeric_limits<_Tp>::digits;

  if (__x == 0) return _Nd;

  constexpr auto _Nd_ull = numeric_limits<unsigned long long>::digits;
  constexpr auto _Nd_ul = numeric_limits<unsigned long>::digits;
  constexpr auto _Nd_u = numeric_limits<unsigned>::digits;

  if _GLIBCXX17_CONSTEXPR (_Nd <= _Nd_u) {
    constexpr int __diff = _Nd_u - _Nd;
    return __builtin_clz(__x) - __diff;
  } else if _GLIBCXX17_CONSTEXPR (_Nd <= _Nd_ul) {
    constexpr int __diff = _Nd_ul - _Nd;
    return __builtin_clzl(__x) - __diff;
  } else if _GLIBCXX17_CONSTEXPR (_Nd <= _Nd_ull) {
    constexpr int __diff = _Nd_ull - _Nd;
    return __builtin_clzll(__x) - __diff;
  } else  // (_Nd > _Nd_ull)
  {
    static_assert(_Nd <= (2 * _Nd_ull),
                  "Maximum supported integer size is 128-bit");

    unsigned long long __high = __x >> _Nd_ull;
    if (__high != 0) {
      constexpr int __diff = (2 * _Nd_ull) - _Nd;
      return __builtin_clzll(__high) - __diff;
    }
    constexpr auto __max_ull = numeric_limits<unsigned long long>::max();
    unsigned long long __low = __x & __max_ull;
    return (_Nd - _Nd_ull) + __builtin_clzll(__low);
  }
}

template <typename _Tp> constexpr int __countr_zero(_Tp __x) noexcept {
  constexpr auto _Nd = numeric_limits<_Tp>::digits;

  if (__x == 0) return _Nd;

  constexpr auto _Nd_ull = numeric_limits<unsigned long long>::digits;
  constexpr auto _Nd_ul = numeric_limits<unsigned long>::digits;
  constexpr auto _Nd_u = numeric_limits<unsigned>::digits;

  if _GLIBCXX17_CONSTEXPR (_Nd <= _Nd_u)
    return __builtin_ctz(__x);
  else if _GLIBCXX17_CONSTEXPR (_Nd <= _Nd_ul)
    return __builtin_ctzl(__x);
  else if _GLIBCXX17_CONSTEXPR (_Nd <= _Nd_ull)
    return __builtin_ctzll(__x);
  else  // (_Nd > _Nd_ull)
  {
    static_assert(_Nd <= (2 * _Nd_ull),
                  "Maximum supported integer size is 128-bit");

    constexpr auto __max_ull = numeric_limits<unsigned long long>::max();
    unsigned long long __low = __x & __max_ull;
    if (__low != 0) return __builtin_ctzll(__low);
    unsigned long long __high = __x >> _Nd_ull;
    return __builtin_ctzll(__high) + _Nd_ull;
  }
}

template <typename _Tp> constexpr int __popcount(_Tp __x) noexcept {
  constexpr auto _Nd = numeric_limits<_Tp>::digits;

  if (__x == 0) return 0;

  constexpr auto _Nd_ull = numeric_limits<unsigned long long>::digits;
  constexpr auto _Nd_ul = numeric_limits<unsigned long>::digits;
  constexpr auto _Nd_u = numeric_limits<unsigned>::digits;

  if _GLIBCXX17_CONSTEXPR (_Nd <= _Nd_u)
    return __builtin_popcount(__x);
  else if _GLIBCXX17_CONSTEXPR (_Nd <= _Nd_ul)
    return __builtin_popcountl(__x);
  else if _GLIBCXX17_CONSTEXPR (_Nd <= _Nd_ull)
    return __builtin_popcountll(__x);
  else  // (_Nd > _Nd_ull)
  {
    static_assert(_Nd <= (2 * _Nd_ull),
                  "Maximum supported integer size is 128-bit");

    constexpr auto __max_ull = numeric_limits<unsigned long long>::max();
    unsigned long long __low = __x & __max_ull;
    unsigned long long __high = __x >> _Nd_ull;
    return __builtin_popcountll(__low) + __builtin_popcountll(__high);
  }
}

template <typename _Tp> constexpr _Tp __bit_ceil(_Tp __x) noexcept {
  constexpr auto _Nd = numeric_limits<_Tp>::digits;
  if (__x == 0 || __x == 1) return 1;
  auto __shift_exponent = _Nd - __countl_zero((_Tp)(__x - 1u));
#ifdef _GLIBCXX_HAVE_BUILTIN_IS_CONSTANT_EVALUATED
  if (!__builtin_is_constant_evaluated()) {
    __glibcxx_assert(__shift_exponent != numeric_limits<_Tp>::digits);
  }
#endif
  using __promoted_type = decltype(__x << 1);
  if _GLIBCXX17_CONSTEXPR (!is_same<__promoted_type, _Tp>::value) {
    const int __extra_exp = sizeof(__promoted_type) / sizeof(_Tp) / 2;
    __shift_exponent |= (__shift_exponent & _Nd) << __extra_exp;
  }
  return (_Tp)1u << __shift_exponent;
}

template <typename _Tp> constexpr _Tp __bit_floor(_Tp __x) noexcept {
  constexpr auto _Nd = numeric_limits<_Tp>::digits;
  if (__x == 0) return 0;
  return (_Tp)1u << (_Nd - __countl_zero((_Tp)(__x >> 1)));
}

template <typename _Tp> constexpr _Tp __bit_width(_Tp __x) noexcept {
  constexpr auto _Nd = numeric_limits<_Tp>::digits;
  return _Nd - __countl_zero(__x);
}

}  // namespace std

#endif

#endif
#line 12 "src/algebra/convolution/bitxor.hpp"

namespace workspace {

template <class A> A bitwise_fft(A f) {
  size_t len = std::__bit_floor(std::size(f));
  for (size_t p = 1; p < len; p <<= 1) {
    for (size_t i = 0; i < len; i += p << 1) {
      for (size_t j = 0; j < p; ++j) {
        auto t = f[i + j + p];
        f[i + j + p] = f[i + j] - t;
        f[i + j] += t;
      }
    }
  }
  return f;
}

template <class A> A bitwise_ifft(A f) {
  size_t len = std::__bit_floor(std::size(f));
  for (size_t p = len; p != 1; p >>= 1) {
    for (size_t i = 0; i < len; i += p) {
      for (size_t j = 0; j << 1 < p; ++j) {
        auto t = f[i + j + (p >> 1)];
        f[i + j + (p >> 1)] = (f[i + j] - t) / 2;
        (f[i + j] += t) /= 2;
      }
    }
  }
  return f;
}

template <class A> A bitxor_conv(A f, A g) {
  f = bitwise_fft(f);
  g = bitwise_fft(g);
  for (size_t i = 0; i != std::size(f); ++i) f[i] *= g[i];
  f = bitwise_ifft(f);
  return f;
}

}  // namespace workspace

Back to top page