Bit reverse (tools/reverse.hpp)

• View this file on GitHub
• View document part on GitHub
• Last update: 2025-02-10 20:05:30+09:00
• Include: #include "tools/reverse.hpp"

template <typename T>
T reverse(T x, std::size_t n);

It returns $r$ which satisfies the followings.

• $0 \leq r < 2^n$
• For all $i$ such that $0 \leq i < n$, the $i$-th bit of $r$ is equal to the $(n - 1 - i)$-th bit of $x$.

Constraints

• <T> is an integral type
• $n \leq$ std::numeric_limits<T>::digits
• $0 \leq x < 2^n$

Time Complexity

• $O(\log n)$

License

• CC0

Author

• anqooqie

Depends on

• Bit width required to represent a given integer (tools/bit_width.hpp)
• $\left\lfloor \log_2(x) \right\rfloor$ (tools/floor_log2.hpp)
• std::is_integral extended for tools::int128_t and tools::uint128_t (tools/is_integral.hpp)
• std::is_signed extended for tools::int128_t and tools::uint128_t (tools/is_signed.hpp)
• std::make_unsigned extended for tools::int128_t and tools::uint128_t (tools/make_unsigned.hpp)

Verified with

• tests/reverse.test.cpp

Code

#ifndef TOOLS_REVERSE_HPP
#define TOOLS_REVERSE_HPP

#include <type_traits>
#include <limits>
#include <cstddef>
#include <cassert>
#include <cstdint>
#include "tools/floor_log2.hpp"

namespace tools {
  template <typename T>
  ::std::enable_if_t<::std::is_integral_v<T> && !::std::is_signed_v<T> && ::std::numeric_limits<T>::digits == 1, T> reverse(const T x, const ::std::size_t n) {
    assert(n <= ::std::numeric_limits<T>::digits);
    assert(!x || n == 1);
    return x;
  }
  template <typename T>
  ::std::enable_if_t<::std::is_integral_v<T> && !::std::is_signed_v<T> && ::std::numeric_limits<T>::digits == 8, T> reverse(T x, const ::std::size_t n) {
    assert(n <= ::std::numeric_limits<T>::digits);
    assert(x == 0 || ::tools::floor_log2(x) < n);
    x = ((x & UINT8_C(0x55)) << 1) | ((x & UINT8_C(0xAA)) >> 1);
    x = ((x & UINT8_C(0x33)) << 2) | ((x & UINT8_C(0xCC)) >> 2);
    x = ((x & UINT8_C(0x0F)) << 4) | ((x & UINT8_C(0xF0)) >> 4);
    x >>= (::std::numeric_limits<T>::digits - n) & (::std::numeric_limits<T>::digits - 1);
    return x;
  }
  template <typename T>
  ::std::enable_if_t<::std::is_integral_v<T> && !::std::is_signed_v<T> && ::std::numeric_limits<T>::digits == 16, T> reverse(T x, const ::std::size_t n) {
    assert(n <= ::std::numeric_limits<T>::digits);
    assert(x == 0 || ::tools::floor_log2(x) < n);
    x = ((x & UINT16_C(0x5555)) << 1) | ((x & UINT16_C(0xAAAA)) >> 1);
    x = ((x & UINT16_C(0x3333)) << 2) | ((x & UINT16_C(0xCCCC)) >> 2);
    x = ((x & UINT16_C(0x0F0F)) << 4) | ((x & UINT16_C(0xF0F0)) >> 4);
    x = ((x & UINT16_C(0x00FF)) << 8) | ((x & UINT16_C(0xFF00)) >> 8);
    x >>= (::std::numeric_limits<T>::digits - n) & (::std::numeric_limits<T>::digits - 1);
    return x;
  }
  template <typename T>
  ::std::enable_if_t<::std::is_integral_v<T> && !::std::is_signed_v<T> && ::std::numeric_limits<T>::digits == 32, T> reverse(T x, const ::std::size_t n) {
    assert(n <= ::std::numeric_limits<T>::digits);
    assert(x == 0 || ::tools::floor_log2(x) < n);
    x = ((x & UINT32_C(0x55555555)) << 1) | ((x & UINT32_C(0xAAAAAAAA)) >> 1);
    x = ((x & UINT32_C(0x33333333)) << 2) | ((x & UINT32_C(0xCCCCCCCC)) >> 2);
    x = ((x & UINT32_C(0x0F0F0F0F)) << 4) | ((x & UINT32_C(0xF0F0F0F0)) >> 4);
    x = ((x & UINT32_C(0x00FF00FF)) << 8) | ((x & UINT32_C(0xFF00FF00)) >> 8);
    x = ((x & UINT32_C(0x0000FFFF)) << 16) | ((x & UINT32_C(0xFFFF0000)) >> 16);
    x >>= (::std::numeric_limits<T>::digits - n) & (::std::numeric_limits<T>::digits - 1);
    return x;
  }
  template <typename T>
  ::std::enable_if_t<::std::is_integral_v<T> && !::std::is_signed_v<T> && ::std::numeric_limits<T>::digits == 64, T> reverse(T x, const ::std::size_t n) {
    assert(n <= ::std::numeric_limits<T>::digits);
    assert(x == 0 || ::tools::floor_log2(x) < n);
    x = ((x & UINT64_C(0x5555555555555555)) << 1) | ((x & UINT64_C(0xAAAAAAAAAAAAAAAA)) >> 1);
    x = ((x & UINT64_C(0x3333333333333333)) << 2) | ((x & UINT64_C(0xCCCCCCCCCCCCCCCC)) >> 2);
    x = ((x & UINT64_C(0x0F0F0F0F0F0F0F0F)) << 4) | ((x & UINT64_C(0xF0F0F0F0F0F0F0F0)) >> 4);
    x = ((x & UINT64_C(0x00FF00FF00FF00FF)) << 8) | ((x & UINT64_C(0xFF00FF00FF00FF00)) >> 8);
    x = ((x & UINT64_C(0x0000FFFF0000FFFF)) << 16) | ((x & UINT64_C(0xFFFF0000FFFF0000)) >> 16);
    x = ((x & UINT64_C(0x00000000FFFFFFFF)) << 32) | ((x & UINT64_C(0xFFFFFFFF00000000)) >> 32);
    x >>= (::std::numeric_limits<T>::digits - n) & (::std::numeric_limits<T>::digits - 1);
    return x;
  }
  template <typename T>
  ::std::enable_if_t<::std::is_integral_v<T> && ::std::is_signed_v<T>, T> reverse(const T x, const ::std::size_t n) {
    assert(x >= 0);
    return ::tools::reverse(static_cast<::std::make_unsigned_t<T>>(x), n);
  }
}

#endif

#line 1 "tools/reverse.hpp"



#include <type_traits>
#include <limits>
#include <cstddef>
#include <cassert>
#include <cstdint>
#line 1 "tools/floor_log2.hpp"



#line 1 "tools/bit_width.hpp"



#include <bit>
#line 1 "tools/is_integral.hpp"



#line 5 "tools/is_integral.hpp"

namespace tools {
  template <typename T>
  struct is_integral : ::std::is_integral<T> {};

  template <typename T>
  inline constexpr bool is_integral_v = ::tools::is_integral<T>::value;
}


#line 1 "tools/is_signed.hpp"



#line 5 "tools/is_signed.hpp"

namespace tools {
  template <typename T>
  struct is_signed : ::std::is_signed<T> {};

  template <typename T>
  inline constexpr bool is_signed_v = ::tools::is_signed<T>::value;
}


#line 1 "tools/make_unsigned.hpp"



#line 5 "tools/make_unsigned.hpp"

namespace tools {
  template <typename T>
  struct make_unsigned : ::std::make_unsigned<T> {};

  template <typename T>
  using make_unsigned_t = typename ::tools::make_unsigned<T>::type;
}


#line 10 "tools/bit_width.hpp"

namespace tools {
  template <typename T>
  constexpr int bit_width(T) noexcept;

  template <typename T>
  constexpr int bit_width(const T x) noexcept {
    static_assert(::tools::is_integral_v<T> && !::std::is_same_v<::std::remove_cv_t<T>, bool>);
    if constexpr (::tools::is_signed_v<T>) {
      assert(x >= 0);
      return ::tools::bit_width<::tools::make_unsigned_t<T>>(x);
    } else {
      return ::std::bit_width(x);
    }
  }
}


#line 6 "tools/floor_log2.hpp"

namespace tools {
  template <typename T>
  constexpr T floor_log2(T x) noexcept {
    assert(x > 0);
    return ::tools::bit_width(x) - 1;
  }
}


#line 10 "tools/reverse.hpp"

namespace tools {
  template <typename T>
  ::std::enable_if_t<::std::is_integral_v<T> && !::std::is_signed_v<T> && ::std::numeric_limits<T>::digits == 1, T> reverse(const T x, const ::std::size_t n) {
    assert(n <= ::std::numeric_limits<T>::digits);
    assert(!x || n == 1);
    return x;
  }
  template <typename T>
  ::std::enable_if_t<::std::is_integral_v<T> && !::std::is_signed_v<T> && ::std::numeric_limits<T>::digits == 8, T> reverse(T x, const ::std::size_t n) {
    assert(n <= ::std::numeric_limits<T>::digits);
    assert(x == 0 || ::tools::floor_log2(x) < n);
    x = ((x & UINT8_C(0x55)) << 1) | ((x & UINT8_C(0xAA)) >> 1);
    x = ((x & UINT8_C(0x33)) << 2) | ((x & UINT8_C(0xCC)) >> 2);
    x = ((x & UINT8_C(0x0F)) << 4) | ((x & UINT8_C(0xF0)) >> 4);
    x >>= (::std::numeric_limits<T>::digits - n) & (::std::numeric_limits<T>::digits - 1);
    return x;
  }
  template <typename T>
  ::std::enable_if_t<::std::is_integral_v<T> && !::std::is_signed_v<T> && ::std::numeric_limits<T>::digits == 16, T> reverse(T x, const ::std::size_t n) {
    assert(n <= ::std::numeric_limits<T>::digits);
    assert(x == 0 || ::tools::floor_log2(x) < n);
    x = ((x & UINT16_C(0x5555)) << 1) | ((x & UINT16_C(0xAAAA)) >> 1);
    x = ((x & UINT16_C(0x3333)) << 2) | ((x & UINT16_C(0xCCCC)) >> 2);
    x = ((x & UINT16_C(0x0F0F)) << 4) | ((x & UINT16_C(0xF0F0)) >> 4);
    x = ((x & UINT16_C(0x00FF)) << 8) | ((x & UINT16_C(0xFF00)) >> 8);
    x >>= (::std::numeric_limits<T>::digits - n) & (::std::numeric_limits<T>::digits - 1);
    return x;
  }
  template <typename T>
  ::std::enable_if_t<::std::is_integral_v<T> && !::std::is_signed_v<T> && ::std::numeric_limits<T>::digits == 32, T> reverse(T x, const ::std::size_t n) {
    assert(n <= ::std::numeric_limits<T>::digits);
    assert(x == 0 || ::tools::floor_log2(x) < n);
    x = ((x & UINT32_C(0x55555555)) << 1) | ((x & UINT32_C(0xAAAAAAAA)) >> 1);
    x = ((x & UINT32_C(0x33333333)) << 2) | ((x & UINT32_C(0xCCCCCCCC)) >> 2);
    x = ((x & UINT32_C(0x0F0F0F0F)) << 4) | ((x & UINT32_C(0xF0F0F0F0)) >> 4);
    x = ((x & UINT32_C(0x00FF00FF)) << 8) | ((x & UINT32_C(0xFF00FF00)) >> 8);
    x = ((x & UINT32_C(0x0000FFFF)) << 16) | ((x & UINT32_C(0xFFFF0000)) >> 16);
    x >>= (::std::numeric_limits<T>::digits - n) & (::std::numeric_limits<T>::digits - 1);
    return x;
  }
  template <typename T>
  ::std::enable_if_t<::std::is_integral_v<T> && !::std::is_signed_v<T> && ::std::numeric_limits<T>::digits == 64, T> reverse(T x, const ::std::size_t n) {
    assert(n <= ::std::numeric_limits<T>::digits);
    assert(x == 0 || ::tools::floor_log2(x) < n);
    x = ((x & UINT64_C(0x5555555555555555)) << 1) | ((x & UINT64_C(0xAAAAAAAAAAAAAAAA)) >> 1);
    x = ((x & UINT64_C(0x3333333333333333)) << 2) | ((x & UINT64_C(0xCCCCCCCCCCCCCCCC)) >> 2);
    x = ((x & UINT64_C(0x0F0F0F0F0F0F0F0F)) << 4) | ((x & UINT64_C(0xF0F0F0F0F0F0F0F0)) >> 4);
    x = ((x & UINT64_C(0x00FF00FF00FF00FF)) << 8) | ((x & UINT64_C(0xFF00FF00FF00FF00)) >> 8);
    x = ((x & UINT64_C(0x0000FFFF0000FFFF)) << 16) | ((x & UINT64_C(0xFFFF0000FFFF0000)) >> 16);
    x = ((x & UINT64_C(0x00000000FFFFFFFF)) << 32) | ((x & UINT64_C(0xFFFFFFFF00000000)) >> 32);
    x >>= (::std::numeric_limits<T>::digits - n) & (::std::numeric_limits<T>::digits - 1);
    return x;
  }
  template <typename T>
  ::std::enable_if_t<::std::is_integral_v<T> && ::std::is_signed_v<T>, T> reverse(const T x, const ::std::size_t n) {
    assert(x >= 0);
    return ::tools::reverse(static_cast<::std::make_unsigned_t<T>>(x), n);
  }
}

Back to top page