$2^{\left\lceil \log_2(x) \right\rceil}$ (tools/bit_ceil.hpp)

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

template <typename T>
constexpr T bit_ceil(T x);

It returns the following value.

\[\begin{align*} \left\{\begin{array}{ll} 1 & \text{(if $x = 0$)}\\ 2^{\lceil \log_2(x) \rceil} & \text{(if $x > 0$)} \end{array}\right.& \end{align*}\]

Constraints

<T> is a built-in integral type, tools::int128_t or tools::uint128_t.
$x \geq 0$
If $x > 0$, $2^{\lceil \log_2(x) \rceil}$ is representable in type T.

Time Complexity

$O(\log\log x)$

License

Author

anqooqie

Depends on

Required by

Verified with

Code

#ifndef TOOLS_BIT_CEIL_HPP
#define TOOLS_BIT_CEIL_HPP

#include <bit>
#include <cassert>
#include <type_traits>
#include "tools/is_integral.hpp"
#include "tools/is_signed.hpp"
#include "tools/make_unsigned.hpp"

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

  template <typename T>
  constexpr T bit_ceil(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_ceil<::tools::make_unsigned_t<T>>(x);
    } else {
      return ::std::bit_ceil(x);
    }
  }
}

#endif

#line 1 "tools/bit_ceil.hpp"



#include <bit>
#include <cassert>
#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 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_ceil.hpp"

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

  template <typename T>
  constexpr T bit_ceil(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_ceil<::tools::make_unsigned_t<T>>(x);
    } else {
      return ::std::bit_ceil(x);
    }
  }
}