data_structure/bit_vector.hpp

• View this file on GitHub
• Last update: 2022-07-22 12:46:12+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 6 "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