data_structure/bit_vector.hpp

• View this file on GitHub
• Last update: 2024-07-18 16:56:22+09:00
• Include: #include "data_structure/bit_vector.hpp"

Depends on

• template/bitop.hpp

Required by

• data_structure/wavelet_matrix.hpp

Verified with

• data_structure/test/range_kth_smallest.test.cpp
• data_structure/test/static_range_frequency.test.cpp
• data_structure/test/wavelet_matrix.test.cpp

Code

#pragma once
#include <vector>
#include "../template/bitop.hpp"

class BitVector {
    static constexpr int WIDTH = 64;

    int n;
    std::vector<unsigned long long> bits;
    std::vector<unsigned long long> sum;
    int zeros;

public:
    BitVector(int _n)
        : n(_n), bits(n / WIDTH + 1, 0), sum(n / WIDTH + 1, 0), zeros(0) {}

    void rev(int idx) { bits[idx / WIDTH] ^= 1ULL << (idx % WIDTH); }

    bool operator[](int idx) const {
        return (bits[idx / WIDTH] & (1ULL << (idx % WIDTH))) != 0;
    }

    void build() {
        for (int i = 1; i < (int)sum.size(); ++i) {
            sum[i] = sum[i - 1] + popcount(bits[i - 1]);
        }
        zeros = rank0(n);
    }

    int rank0(int n) const { return n - rank1(n); }
    int rank1(int n) const {
        return sum[n / WIDTH] +
               popcount(
                   mask_n(bits[n / WIDTH], (unsigned long long)(n % WIDTH)));
    }
    int all_zeros() const { return zeros; }
};

#line 2 "data_structure/bit_vector.hpp"
#include <vector>
#line 2 "template/bitop.hpp"

template <typename T, typename U>
bool ith_bit(T n, U i) {
    return (n & ((T)1 << i)) != 0;
}

int popcount(int x) { return __builtin_popcount(x); }
unsigned popcount(unsigned x) { return __builtin_popcount(x); }
long long popcount(long long x) { return __builtin_popcountll(x); }
unsigned long long popcount(unsigned long long x) {
    return __builtin_popcountll(x);
}

// x must not be 0
int clz(int x) { return __builtin_clz(x); }
unsigned clz(unsigned x) { return __builtin_clz(x); }
long long clz(long long x) { return __builtin_clzll(x); }
unsigned long long clz(unsigned long long x) { return __builtin_clzll(x); }

// x must not be 0
int ctz(int x) { return __builtin_ctz(x); }
unsigned ctz(unsigned int x) { return __builtin_ctz(x); }
long long ctz(long long x) { return __builtin_ctzll(x); }
unsigned long long ctz(unsigned long long x) { return __builtin_ctzll(x); }

int floor_log2(int x) { return 31 - clz(x); }
unsigned floor_log2(unsigned x) { return 31 - clz(x); }
long long floor_log2(long long x) { return 63 - clz(x); }
unsigned long long floor_log2(unsigned long long x) { return 63 - clz(x); }

template <typename T>
T mask_n(T x, T n) {
    T mask = ((T)1 << n) - 1;
    return x & mask;
}
#line 4 "data_structure/bit_vector.hpp"

class BitVector {
    static constexpr int WIDTH = 64;

    int n;
    std::vector<unsigned long long> bits;
    std::vector<unsigned long long> sum;
    int zeros;

public:
    BitVector(int _n)
        : n(_n), bits(n / WIDTH + 1, 0), sum(n / WIDTH + 1, 0), zeros(0) {}

    void rev(int idx) { bits[idx / WIDTH] ^= 1ULL << (idx % WIDTH); }

    bool operator[](int idx) const {
        return (bits[idx / WIDTH] & (1ULL << (idx % WIDTH))) != 0;
    }

    void build() {
        for (int i = 1; i < (int)sum.size(); ++i) {
            sum[i] = sum[i - 1] + popcount(bits[i - 1]);
        }
        zeros = rank0(n);
    }

    int rank0(int n) const { return n - rank1(n); }
    int rank1(int n) const {
        return sum[n / WIDTH] +
               popcount(
                   mask_n(bits[n / WIDTH], (unsigned long long)(n % WIDTH)));
    }
    int all_zeros() const { return zeros; }
};

Back to top page