bit/msb.hpp

• View this file on GitHub
• Last update: 2021-12-09 20:34:48+09:00
• Include: #include "bit/msb.hpp"

Required by

• segment_tree/lazy_segment_tree.hpp
• sparse_table/disjoint_sparse_table.hpp

Verified with

• test/aoj/DSL2F_1.test.cpp
• test/aoj/DSL2G.test.cpp
• test/aoj/DSL2H.test.cpp
• test/aoj/DSL2I.test.cpp
• test/aoj/bits.test.cpp
• test/yosupo/range_affine_range_sum.test.cpp
• test/yosupo/static_range_sum.test.cpp

Code

#ifndef MSB_HPP
#define MSB_HPP

#include <cstdint>

inline uint32_t msb32_(uint32_t bit) {
    bit |= bit >> 1;
    bit |= bit >> 2;
    bit |= bit >> 4;
    bit |= bit >> 8;
    bit |= bit >> 16;
    return bit ^ (bit >> 1);
};
inline uint32_t msb32(uint32_t x) {
    if (x == 0) return 0;
#ifdef __has_builtin
    return 1u << (31 - __builtin_clz(x));
#else
    return msb32_(x);
#endif
};

inline uint64_t msb64_(uint64_t bit) {
    bit |= bit >> 1;
    bit |= bit >> 2;
    bit |= bit >> 4;
    bit |= bit >> 8;
    bit |= bit >> 16;
    bit |= bit >> 32;
    return bit ^ (bit >> 1);
};
inline uint64_t msb64(uint64_t x) {
    if (x == 0) return 0;
#ifdef __has_builtin
    return 1ull << (63 - __builtin_clzll(x));
#else
    return msb64_(x);
#endif
};

#endif

#line 1 "bit/msb.hpp"



#include <cstdint>

inline uint32_t msb32_(uint32_t bit) {
    bit |= bit >> 1;
    bit |= bit >> 2;
    bit |= bit >> 4;
    bit |= bit >> 8;
    bit |= bit >> 16;
    return bit ^ (bit >> 1);
};
inline uint32_t msb32(uint32_t x) {
    if (x == 0) return 0;
#ifdef __has_builtin
    return 1u << (31 - __builtin_clz(x));
#else
    return msb32_(x);
#endif
};

inline uint64_t msb64_(uint64_t bit) {
    bit |= bit >> 1;
    bit |= bit >> 2;
    bit |= bit >> 4;
    bit |= bit >> 8;
    bit |= bit >> 16;
    bit |= bit >> 32;
    return bit ^ (bit >> 1);
};
inline uint64_t msb64(uint64_t x) {
    if (x == 0) return 0;
#ifdef __has_builtin
    return 1ull << (63 - __builtin_clzll(x));
#else
    return msb64_(x);
#endif
};

Back to top page