comp-library

This documentation is automatically generated by online-judge-tools/verification-helper

View the Project on GitHub luzhiled1333/comp-library

:heavy_check_mark: 最下位bitから連続する 0 の数 (counting trailing 0s, countr_zero)
(src/utility/bit/count-trailing-0s.hpp)

countr_zero

usize countr_zero(u64 n)

n を二進表記したとき、右からいくつ連続した $0$ が続くかを返す。

$n = 0$ のときは $64$ が返る。

計算量

制約

C++20 以降では std::countr_zero(T n) を使用すること。

Depends on

Required by

Verified with

Code

#pragma once

#include "src/cpp-template/header/int-alias.hpp"
#include "src/cpp-template/header/size-alias.hpp"
#include "src/utility/bit/popcount.hpp"

#include <cassert>

namespace luz {

  usize countr_zero(u64 x) {
    assert(__cplusplus <= 201703L);

    if (x == 0) {
      return 64;
    }

#ifdef __GNUC__
    return __builtin_ctzll(x);
#endif

    return popcount((x & -x) - 1);
  }

} // namespace luz
#line 2 "src/utility/bit/count-trailing-0s.hpp"

#line 2 "src/cpp-template/header/int-alias.hpp"

#include <cstdint>

namespace luz {

  using i32  = std::int32_t;
  using i64  = std::int64_t;
  using i128 = __int128_t;

  using u32  = std::uint32_t;
  using u64  = std::uint64_t;
  using u128 = __uint128_t;

} // namespace luz
#line 2 "src/cpp-template/header/size-alias.hpp"

#include <cstddef>

namespace luz {

  using isize = std::ptrdiff_t;
  using usize = std::size_t;

} // namespace luz
#line 2 "src/utility/bit/popcount.hpp"

#line 5 "src/utility/bit/popcount.hpp"

#include <cassert>

namespace luz {

  usize popcount(u64 x) {
    assert(__cplusplus <= 201703L);

#ifdef __GNUC__
    return __builtin_popcountll(x);
#endif

    x -= (x >> 1) & 0x5555555555555555;
    x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333);
    x += (x >> 4) & 0x0f0f0f0f0f0f0f0f;
    return x * 0x0101010101010101 >> 56 & 0x7f;
  }

} // namespace luz
#line 6 "src/utility/bit/count-trailing-0s.hpp"

#line 8 "src/utility/bit/count-trailing-0s.hpp"

namespace luz {

  usize countr_zero(u64 x) {
    assert(__cplusplus <= 201703L);

    if (x == 0) {
      return 64;
    }

#ifdef __GNUC__
    return __builtin_ctzll(x);
#endif

    return popcount((x & -x) - 1);
  }

} // namespace luz
Back to top page