algo/utils/bits.h

• View this file on GitHub
• Last update: 2024-12-10 21:37:51-05:00

Depends on

• algo/common.h

Required by

• algo/ds/sparse_table.h
• algo/graph/lca.h
• main.cpp

Verified with

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

Code

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

namespace algo::utils {

// Returns number of set bits in x
constexpr int popcnt(int64_t x) {
    return __builtin_popcountll(x);
}
// Returns floor(log_2(x))
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>
#endif

namespace algo {}

#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#line 3 "algo/utils/bits.h"

namespace algo::utils {

// Returns number of set bits in x
constexpr int popcnt(int64_t x) {
    return __builtin_popcountll(x);
}
// Returns floor(log_2(x))
constexpr int lg2(uint64_t x) {
    return std::bit_width(x) - 1;
}

} // namespace algo::utils

Back to top page