compact_data_structure/bit_vector.hpp

• View this file on GitHub
• Last update: 2022-09-01 14:18:35+09:00
• Include: #include "compact_data_structure/bit_vector.hpp"

Depends on

• bit/pop_count.hpp

Code

#ifndef BIT_VECTOR_HPP
#define BIT_VECTOR_HPP

#include <cstdint>
#include <string>
#include <vector>

#include "../bit/pop_count.hpp"

struct BitVector {
    using u64 = uint64_t;
    using u32 = uint32_t;
    using u8 = uint8_t;

    std::vector<u32> bit;
    std::vector<u32> chunk;

    BitVector() = default;
    explicit BitVector(int len)
        : bit((len + 31) / 32, 0), chunk((len + 31) / 32, 0){};
    BitVector(std::vector<bool> v)
        : bit((v.size() + 31) / 32, 0), chunk((v.size() + 31) / 32, 0) {
        for (int i = 0; i < v.size(); i++) {
            if (v[i]) set(i);
        }
    };
    BitVector(std::string s)
        : bit((s.size() + 31) / 32, 0), chunk((s.size() + 31) / 32, 0) {
        for (int i = 0; i < s.size(); i++) {
            if (s[i] == '1') set(i);
        }
    };

    bool operator[](int k) {
        return bool((bit[k / 32] >> (k & 31)) & 1);
    };

    void set(int k) {
        bit[k / 32] |= 1u << (k & 31);
    };
    void build() {
        for (int i = 1; i < size(); i++) {
            chunk[i] = chunk[i - 1] + popcnt32(bit[i - 1]);
        }
    };

    int size() {
        return bit.size();
    };

    // count number of 1 in [0, k)
    int rank1(int k) {
        return chunk[k / 32] + popcnt32(bit[k / 32] & ~((~0u) << (k & 31)));
    };
    // count number of 0 in [0, k)
    int rank0(int k) {
        return k - rank1(k);
    };
    int select1(int k) {
        int l = 0;
        int r = size();
        int m;
        while (r - l > 1) {
            m = (l + r) >> 1;
            if (rank1(m) >= k)
                r = m;
            else
                l = m;
        }
        return r - 1;
    };
    int select0(int k) {
        int l = 0;
        int r = size();
        int m;
        while (r - l > 1) {
            m = (l + r) >> 1;
            if (rank0(m) >= k)
                r = m;
            else
                l = m;
        }
        return r - 1;
    };
};

#endif

#line 1 "compact_data_structure/bit_vector.hpp"



#include <cstdint>
#include <string>
#include <vector>

#line 1 "bit/pop_count.hpp"



#line 5 "bit/pop_count.hpp"

inline int popcnt64_(uint64_t bits) {
    bits = (bits & 0x5555555555555555) + (bits >> 1 & 0x5555555555555555);
    bits = (bits & 0x3333333333333333) + (bits >> 2 & 0x3333333333333333);
    bits = (bits & 0x0f0f0f0f0f0f0f0f) + (bits >> 4 & 0x0f0f0f0f0f0f0f0f);
    bits = (bits & 0x00ff00ff00ff00ff) + (bits >> 8 & 0x00ff00ff00ff00ff);
    bits = (bits & 0x0000ffff0000ffff) + (bits >> 16 & 0x0000ffff0000ffff);
    bits = (bits & 0x00000000ffffffff) + (bits >> 32 & 0x00000000ffffffff);
    return bits;
};
inline int popcnt64(uint64_t bits) {
#ifdef __has_builtin
    return __builtin_popcountll(bits);
#else
    return popcnt64_(bits);
#endif
};

inline int popcnt32_(uint32_t bits) {
    bits = (bits & 0x55555555) + (bits >> 1 & 0x55555555);
    bits = (bits & 0x33333333) + (bits >> 2 & 0x33333333);
    bits = (bits & 0x0f0f0f0f) + (bits >> 4 & 0x0f0f0f0f);
    bits = (bits & 0x00ff00ff) + (bits >> 8 & 0x00ff00ff);
    bits = (bits & 0x0000ffff) + (bits >> 16 & 0x0000ffff);
    return bits;
};
inline int popcnt32(uint32_t bits) {
#ifdef __has_builtin
    return __builtin_popcount(bits);
#else
    return popcnt32_(bits);
#endif
};


#line 9 "compact_data_structure/bit_vector.hpp"

struct BitVector {
    using u64 = uint64_t;
    using u32 = uint32_t;
    using u8 = uint8_t;

    std::vector<u32> bit;
    std::vector<u32> chunk;

    BitVector() = default;
    explicit BitVector(int len)
        : bit((len + 31) / 32, 0), chunk((len + 31) / 32, 0){};
    BitVector(std::vector<bool> v)
        : bit((v.size() + 31) / 32, 0), chunk((v.size() + 31) / 32, 0) {
        for (int i = 0; i < v.size(); i++) {
            if (v[i]) set(i);
        }
    };
    BitVector(std::string s)
        : bit((s.size() + 31) / 32, 0), chunk((s.size() + 31) / 32, 0) {
        for (int i = 0; i < s.size(); i++) {
            if (s[i] == '1') set(i);
        }
    };

    bool operator[](int k) {
        return bool((bit[k / 32] >> (k & 31)) & 1);
    };

    void set(int k) {
        bit[k / 32] |= 1u << (k & 31);
    };
    void build() {
        for (int i = 1; i < size(); i++) {
            chunk[i] = chunk[i - 1] + popcnt32(bit[i - 1]);
        }
    };

    int size() {
        return bit.size();
    };

    // count number of 1 in [0, k)
    int rank1(int k) {
        return chunk[k / 32] + popcnt32(bit[k / 32] & ~((~0u) << (k & 31)));
    };
    // count number of 0 in [0, k)
    int rank0(int k) {
        return k - rank1(k);
    };
    int select1(int k) {
        int l = 0;
        int r = size();
        int m;
        while (r - l > 1) {
            m = (l + r) >> 1;
            if (rank1(m) >= k)
                r = m;
            else
                l = m;
        }
        return r - 1;
    };
    int select0(int k) {
        int l = 0;
        int r = size();
        int m;
        while (r - l > 1) {
            m = (l + r) >> 1;
            if (rank0(m) >= k)
                r = m;
            else
                l = m;
        }
        return r - 1;
    };
};

Back to top page