Number of trailing zeros (tools/countr_zero.hpp)

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

template <typename T>
constexpr int countr_zero(T x) noexcept;

It returns the number of trailing zeros. (e.g., countr_zero(0b10100) is $2$) If $x$ is $0$, it returns std::numeric_limits<T>::digits.

Constraints

<T> is a built-in integral type, tools::int128_t or tools::uint128_t.
$x \geq 0$

Time Complexity

$O(1)$

References

C++11で実装するNTZとNLZ

License

Author

anqooqie

Depends on

Required by

Verified with

Code

#ifndef TOOLS_COUNTR_ZERO_HPP
#define TOOLS_COUNTR_ZERO_HPP

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

namespace tools {
  template <typename T>
  constexpr int countr_zero(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 ::std::min(::tools::countr_zero<::tools::make_unsigned_t<T>>(x), ::std::numeric_limits<T>::digits);
    } else {
      return ::std::countr_zero(x);
    }
  }
}

#endif

#line 1 "tools/countr_zero.hpp"



#include <algorithm>
#include <bit>
#include <cassert>
#include <limits>
#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 12 "tools/countr_zero.hpp"

namespace tools {
  template <typename T>
  constexpr int countr_zero(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 ::std::min(::tools::countr_zero<::tools::make_unsigned_t<T>>(x), ::std::numeric_limits<T>::digits);
    } else {
      return ::std::countr_zero(x);
    }
  }
}