algo/utils/bits.h

• View this file on GitHub
• Last update: 2026-09-28 20:05:44-04:00

Depends on

• algo/common.h

Required by

• algo/ds/lazy_segtree.h
• algo/ds/sparse_table.h
• algo/graph/lca.h

Verified with

• verify/ds/lazy_segtree.test.cpp
• verify/ds/sparse_table.test.cpp
• verify/graph/tree_lca.test.cpp

Code

#pragma once
#include "algo/common.h"

namespace algo::utils {

// Number of 1 bits in x
constexpr int popcnt(int64_t x) {
    return __builtin_popcountll(x);
}
// floor(log2(x)); -1 for x = 0
constexpr int lg2(uint64_t x) {
    return std::bit_width(x) - 1;
}

} // namespace algo::utils

#line 2 "algo/common.h"
#ifndef PREPROCESS
#include <bits/stdc++.h>
#include <cassert>
#endif

// Declared here so `using namespace algo;` works with no other includes.
namespace algo {}
#line 3 "algo/utils/bits.h"

namespace algo::utils {

// Number of 1 bits in x
constexpr int popcnt(int64_t x) {
    return __builtin_popcountll(x);
}
// floor(log2(x)); -1 for x = 0
constexpr int lg2(uint64_t x) {
    return std::bit_width(x) - 1;
}

} // namespace algo::utils

Back to top page