atcoder/internal_bit.hpp

• View this file on GitHub
• Last update: 2025-07-04 15:57:54+09:00
• Include: #include "atcoder/internal_bit.hpp"

Required by

• atcoder/convolution.hpp
• atcoder/lazysegtree.hpp
• atcoder/segtree.hpp
• FormalPowerSeries.cpp
• Series.cpp
• TaylorShift.cpp
• test/atcoder/convolution.hpp
• test/atcoder/lazysegtree.hpp
• test/atcoder/segtree.hpp

Verified with

• test/FPSprod.test.cpp
• test/Series/Bell.test.cpp
• test/Series/Bernoulli.test.cpp
• test/Series/Partition.test.cpp
• test/Series/StirlingFirst.test.cpp
• test/Series/StirlingSecond.test.cpp
• test/Series/StirlingSecondFixedK.test.cpp
• test/TaylorShift.test.cpp

Code

#ifndef ATCODER_INTERNAL_BITOP_HPP
#define ATCODER_INTERNAL_BITOP_HPP 1

#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`
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

#endif  // ATCODER_INTERNAL_BITOP_HPP

#line 1 "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`
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