atcoder/internal_bit.hpp

• View this file on GitHub
• Last update: 2020-10-30 19:21:58+09:00
• Include: #include "atcoder/internal_bit.hpp"

Required by

• DataStructure/LazySegmentTree.cpp
• DataStructure/SegmentTree.cpp
• atcoder/convolution.hpp
• atcoder/lazysegtree.hpp
• atcoder/segtree.hpp

Verified with

• test/HLD_edge.test.cpp
• test/HLD_subtree_edge.test.cpp
• test/HLD_vertex.test.cpp
• test/RangeAddRangeMin.test.cpp
• test/RangeAddRangeSum.test.cpp
• test/RangeMinQuery.test.cpp
• test/RangeSumQuery.test.cpp
• test/RangeUpdateRangeMin.test.cpp
• test/RangeUpdateRangeSum.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