Bit Ceil
(math/bit_ceil.hpp)

• View this file on GitHub
• Last update: 2026-06-15 01:47:39+09:00
• Include: #include "math/bit_ceil.hpp"

Overview

A math utility function that calculates the smallest power of two that is greater than or equal to a given number n.

This is frequently used internally to determine the optimal underlying array size for complete binary tree structures (like Segment Trees) so that their length is perfectly aligned to a power of 2.

API

template <typename T>
constexpr T bit_ceil(T n);

T is both the argument and return type. It must be an integer-like type that supports comparison, left shift, and construction from 1.

The function returns the smallest power of two greater than or equal to n. If n <= 1, it returns T(1). The result must be representable by T.

Complexity

The running time is $O(\log n)$ and the additional memory usage is $O(1)$.

Example

#include "math/bit_ceil.hpp"

#include <iostream>

int main() {
    std::cout << m1une::math::bit_ceil(13) << "\n"; // 16
}

Required by

• Merge Sort Tree (ds/range_query/merge_sort_tree.hpp)
• Range Sort Range Composite (ds/range_query/range_sort_range_composite.hpp)
• Dual Segment Tree (ds/segtree/dual_segtree.hpp)
• Dual Segtree 2D (ds/segtree/dual_segtree_2d.hpp)
• Lazy Segment Tree (ds/segtree/lazy_segtree.hpp)
• Rollback Lazy Segment Tree (ds/segtree/rollback_lazy_segtree.hpp)
• Rollback Segment Tree Beats (ds/segtree/rollback_segtree_beats.hpp)
• Segment Tree (ds/segtree/segtree.hpp)
• Segtree 2D (ds/segtree/segtree_2d.hpp)
• Generic Segment Tree Beats! (ds/segtree/segtree_beats.hpp)
• Math All (math/all.hpp)

Verified with

• verify/acted_monoid/range_bitwise_and_or_xor_range_sum.test.cpp
• verify/beats_acted_monoid/range_bitwise_and_or_range_sum.test.cpp
• verify/beats_acted_monoid/range_chmin_chmax_add_range_sum.test.cpp
• verify/ds/range_query/merge_sort_tree.test.cpp
• verify/ds/range_query/merge_sort_tree_sum.test.cpp
• verify/ds/range_query/range_sort_range_composite.test.cpp
• verify/ds/rollback_counterparts.test.cpp
• verify/ds/segtree/dual_segtree.test.cpp
• verify/ds/segtree/dual_segtree_2d.test.cpp
• verify/ds/segtree/lazy_segtree.test.cpp
• verify/ds/segtree/range_add_range_min.test.cpp
• verify/ds/segtree/range_update_range_product.test.cpp
• verify/ds/segtree/segtree.test.cpp
• verify/ds/segtree/segtree_2d.test.cpp
• verify/ds/segtree/segtree_beats.test.cpp
• verify/math/math_algorithms.test.cpp

Code

#ifndef M1UNE_BIT_CEIL_HPP
#define M1UNE_BIT_CEIL_HPP 1

namespace m1une {
namespace math {

template <typename T>
constexpr T bit_ceil(T n) {
    if (n <= 1) return 1;
    T x = 1;
    while (x < n) x <<= 1;
    return x;
}

}  // namespace math
}  // namespace m1une

#endif  // M1UNE_BIT_CEIL_HPP

#line 1 "math/bit_ceil.hpp"



namespace m1une {
namespace math {

template <typename T>
constexpr T bit_ceil(T n) {
    if (n <= 1) return 1;
    T x = 1;
    while (x < n) x <<= 1;
    return x;
}

}  // namespace math
}  // namespace m1une

Back to top page