Topbit
(misc/topbit.hpp)

• View this file on GitHub
• Last update: 2025-12-31 07:11:44+09:00
• Include: #include "misc/topbit.hpp"
• Link: View error logs on GitHub Actions

topbit

int topbit(T x)

最上位に立っているビットの位置を返します。

$x = 0$ のときは $-1$ を返します。

Depends on

• Countl Zero (misc/countl_zero.hpp)

Required by

• Auxiliary Tree (虚树) (graph/auxiliary_tree.hpp)
• Lowest Common Ancestor (最小共通祖先) (graph/lowest_common_ancestor.hpp)
• my_template.hpp
• my_template_int128.hpp

Verified with

• misc/test/bit_operation.test.cpp
• verify/graph/auxiliary_tree.test.cpp
• verify/graph/lowest_common_ancestor_1.test.cpp
• verify/graph/lowest_common_ancestor_2.test.cpp

Code

#pragma once

#include "./countl_zero.hpp"

// topbit
// (000, 001, 010, 011, 100) -> (-1, 0, 1, 1, 2)
int topbit(int x) { return 31 - countl_zero(x); }
int topbit(unsigned int x) { return 31 - countl_zero(x); }
int topbit(long long int x) { return 63 - countl_zero(x); }
int topbit(unsigned long long int x) { return 63 - countl_zero(x); }

#line 2 "misc/topbit.hpp"

#line 2 "misc/countl_zero.hpp"

#if __cplusplus >= 202002L
#include <bit>
#endif

// countl_zero
// (000, 001, 010, 011, 100) -> (32, 31, 30, 30, 29)
#if __cplusplus >= 202002L
using std::countl_zero;
#else
int countl_zero(unsigned int x) {
    return x == 0 ? 32 : __builtin_clz(x);
}
int countl_zero(unsigned long long int x) {
    return x == 0 ? 64 : __builtin_clzll(x);
}
#endif
int countl_zero(int x) { return countl_zero((unsigned int)(x)); }
int countl_zero(long long int x) {
    return countl_zero((unsigned long long int)(x));
}
#line 4 "misc/topbit.hpp"

// topbit
// (000, 001, 010, 011, 100) -> (-1, 0, 1, 1, 2)
int topbit(int x) { return 31 - countl_zero(x); }
int topbit(unsigned int x) { return 31 - countl_zero(x); }
int topbit(long long int x) { return 63 - countl_zero(x); }
int topbit(unsigned long long int x) { return 63 - countl_zero(x); }

Back to top page