Circular shift to the right (tools/rotr.hpp)

(1)

template <typename T, typename U>
T rotr(T x, int n, U s);

It returns $r$ which satisfies the followings.

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

Constraints

<T> is a built-in integral type
<U> is a built-in integral type
$0 \leq n \leq$ std::numeric_limits<T>::digits
$0 \leq x < 2^n$

Time Complexity

$O(1)$

License

Author

anqooqie

(2)

template <typename T, typename U>
T rotr(T x, U s);

It returns $r$ which satisfies the followings.

r.size() == x.size()
Let $n$ be x.size(). For all $i$ such that $0 \leq i < n$, the $(((i - s) \bmod n) + 1)$-th least bit of $r$ is equal to the $(i + 1)$-th least bit of $x$.

Constraints

<T> is std::bitset or tools::dynamic_bitset
<U> is a built-in integral type

Time Complexity

$O(|x|)$

License

Author

anqooqie

Depends on

Verified with

tests/rotr.test.cpp

Code

#ifndef TOOLS_ROTR_HPP
#define TOOLS_ROTR_HPP

#include <cassert>
#include <limits>
#include "tools/mod.hpp"

namespace tools {

  template <typename T, typename U>
  constexpr T rotr(const T x, const int n, U s) {
    assert(0 <= n && n <= ::std::numeric_limits<T>::digits);
    const T mask = (n == ::std::numeric_limits<T>::digits ? ::std::numeric_limits<T>::max() : (T(1) << n) - 1);
    assert(0 <= x && x <= mask);
    if (n == 0) return x;
    s = ::tools::mod(s, n);
    return ((x << ((n - s) % n)) | (x >> s)) & mask;
  }

  template <typename T, typename U>
  T rotr(const T& x, U s) {
    if (x.size() == 0) return x;
    s = ::tools::mod(s, x.size());
    return (x << ((x.size() - s) % x.size())) | (x >> s);
  }
}

#endif

#line 1 "tools/rotr.hpp"



#include <cassert>
#include <limits>
#line 1 "tools/mod.hpp"



#line 5 "tools/mod.hpp"
#include <type_traits>
#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 7 "tools/mod.hpp"

namespace tools {

  template <typename M, typename N> requires (
    ::tools::is_integral_v<M> && !::std::is_same_v<::std::remove_cv_t<M>, bool> &&
    ::tools::is_integral_v<N> && !::std::is_same_v<::std::remove_cv_t<N>, bool>)
  constexpr ::std::common_type_t<M, N> mod(const M a, const N b) noexcept {
    assert(b != 0);

    using UM = ::std::make_unsigned_t<M>;
    using UN = ::std::make_unsigned_t<N>;
    const UM ua = a >= 0 ? a : static_cast<UM>(-(a + 1)) + 1;
    const UN ub = b >= 0 ? b : static_cast<UN>(-(b + 1)) + 1;
    auto r = ua % ub;
    if (a < 0 && r > 0) {
      r = ub - r;
    }
    return r;
  }
}


#line 7 "tools/rotr.hpp"

namespace tools {

  template <typename T, typename U>
  constexpr T rotr(const T x, const int n, U s) {
    assert(0 <= n && n <= ::std::numeric_limits<T>::digits);
    const T mask = (n == ::std::numeric_limits<T>::digits ? ::std::numeric_limits<T>::max() : (T(1) << n) - 1);
    assert(0 <= x && x <= mask);
    if (n == 0) return x;
    s = ::tools::mod(s, n);
    return ((x << ((n - s) % n)) | (x >> s)) & mask;
  }

  template <typename T, typename U>
  T rotr(const T& x, U s) {
    if (x.size() == 0) return x;
    s = ::tools::mod(s, x.size());
    return (x << ((x.size() - s) % x.size())) | (x >> s);
  }
}