seekworser's Library

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

---

Project maintained by seekworser Hosted on GitHub Pages — Theme by mattgraham

atcoder/internal_bit.hpp

• View this file on GitHub
• Last update: 2023-02-28 16:59:41+09:00
• Include: #include "atcoder/internal_bit.hpp"

Required by

• atcoder/convolution.hpp
• atcoder/lazysegtree.hpp
• atcoder/segtree.hpp
• 遅延セグメント木（ラッパー） (competitive/data_structure/lazysegtree.hpp)
• セグメント木（ラッパー） (competitive/data_structure/segtree.hpp)
• HL分解 (Heavy Light Decomposition) (competitive/tree/heavy_light_decomposition.hpp)

Verified with

• online_test/AOJ/DSL_2_F.test.cpp
• online_test/AOJ/DSL_2_G.test.cpp
• online_test/AOJ/DSL_2_H.test.cpp
• online_test/AOJ/DSL_2_I.test.cpp
• online_test/AOJ/GRL_5_C.test.cpp
• online_test/library-checker/lca_hld.test.cpp
• online_test/yukicoder/yuki-399.test.cpp

Code

#pragma once
#ifdef _MSC_VER
#include <intrin.h>
#endif

namespace atcoder {

namespace internal {

// @param n `0 <= n`
// @return minimum non-negative `x` s.t. `n <= 2**x`
int ceil_pow2(int n) {
    int x = 0;
    while ((1U << x) < (unsigned int)(n)) x++;
    return x;
}

// @param n `1 <= n`
// @return minimum non-negative `x` s.t. `(n & (1 << x)) != 0`
constexpr int bsf_constexpr(unsigned int n) {
    int x = 0;
    while (!(n & (1 << x))) x++;
    return x;
}

// @param n `1 <= n`
// @return minimum non-negative `x` s.t. `(n & (1 << x)) != 0`
int bsf(unsigned int n) {
#ifdef _MSC_VER
    unsigned long index;
    _BitScanForward(&index, n);
    return index;
#else
    return __builtin_ctz(n);
#endif
}

}  // namespace internal

}  // namespace atcoder

#line 2 "atcoder/internal_bit.hpp"
#ifdef _MSC_VER
#include <intrin.h>
#endif

namespace atcoder {

namespace internal {

// @param n `0 <= n`
// @return minimum non-negative `x` s.t. `n <= 2**x`
int ceil_pow2(int n) {
    int x = 0;
    while ((1U << x) < (unsigned int)(n)) x++;
    return x;
}

// @param n `1 <= n`
// @return minimum non-negative `x` s.t. `(n & (1 << x)) != 0`
constexpr int bsf_constexpr(unsigned int n) {
    int x = 0;
    while (!(n & (1 << x))) x++;
    return x;
}

// @param n `1 <= n`
// @return minimum non-negative `x` s.t. `(n & (1 << x)) != 0`
int bsf(unsigned int n) {
#ifdef _MSC_VER
    unsigned long index;
    _BitScanForward(&index, n);
    return index;
#else
    return __builtin_ctz(n);
#endif
}

}  // namespace internal

}  // namespace atcoder

Back to top page