cp-algo/util/bit.hpp

• View this file on GitHub
• Last update: 2024-11-14 19:37:39+01:00
• Include: #include "cp-algo/util/bit.hpp"

Required by

• cp-algo/structures/bit_array.hpp
• cp-algo/structures/bitpack.hpp
• cp-algo/structures/fenwick_set.hpp
• cp-algo/util/compress_coords.hpp
• cp-algo/util/sort.hpp

Verified with

• Determinant of Matrix (Mod 2) (verify/structures/bitpack/det_mod_2.test.cpp)
• Inverse Matrix (Mod 2) (verify/structures/bitpack/inv_mod_2.test.cpp)
• Matrix Product (Mod 2) (verify/structures/bitpack/prod_mod_2.test.cpp)
• System of Linear Equations (Mod 2) (verify/structures/bitpack/system_mod_2.test.cpp)
• Ordered Set (verify/structures/fenwick/ordered_set.test.cpp)

Code

#ifndef CP_ALGO_UTIL_BIT_HPP
#define CP_ALGO_UTIL_BIT_HPP
#include <immintrin.h>
#include <cstdint>
#include <array>
#include <bit>
namespace cp_algo {
    template<typename Uint>
    constexpr size_t bit_width = sizeof(Uint) * 8;

    size_t order_of_bit(auto x, size_t k) {
        return k ? std::popcount(x << (bit_width<decltype(x)> - k)) : 0;
    }
    // Requires GCC target("popcnt,bmi2")
    size_t kth_set_bit(uint64_t x, size_t k) {
        return std::countr_zero(_pdep_u64(1ULL << k, x));
    }
    template<int fl = 0>
    void with_bit_floor(size_t n, auto &&callback) {
        if constexpr (fl >= 63) {
            return;
        } else if (n >> (fl + 1)) {
            with_bit_floor<fl + 1>(n, callback);
        } else {
            callback.template operator()<1ULL << fl>();
        }
    }
}
#endif // CP_ALGO_UTIL_BIT_HPP

#line 1 "cp-algo/util/bit.hpp"


#include <immintrin.h>
#include <cstdint>
#include <array>
#include <bit>
namespace cp_algo {
    template<typename Uint>
    constexpr size_t bit_width = sizeof(Uint) * 8;

    size_t order_of_bit(auto x, size_t k) {
        return k ? std::popcount(x << (bit_width<decltype(x)> - k)) : 0;
    }
    // Requires GCC target("popcnt,bmi2")
    size_t kth_set_bit(uint64_t x, size_t k) {
        return std::countr_zero(_pdep_u64(1ULL << k, x));
    }
    template<int fl = 0>
    void with_bit_floor(size_t n, auto &&callback) {
        if constexpr (fl >= 63) {
            return;
        } else if (n >> (fl + 1)) {
            with_bit_floor<fl + 1>(n, callback);
        } else {
            callback.template operator()<1ULL << fl>();
        }
    }
}

Back to top page