Bit vector (tools/bit_vector.hpp)

• View this file on GitHub
• View document part on GitHub
• Last update: 2023-06-25 00:33:03+09:00
• Include: #include "tools/bit_vector.hpp"
• Link: https://nyaannyaan.github.io/library/data-structure-2d/wavelet-matrix.hpp.html

It is a bit vector.

License

• CC0 1.0 Universal

Author

• Nyaan

Constructor

bit_vector bv(int n);

It creates a bit vector of length $n$ filled with $0$.

Constraints

• $n \geq 0$

Time Complexity

• $O(n)$

init

void bv.init(int n);

It makes bv a bit vector of length $n$ filled with $0$.

Constraints

• $n \geq 0$

Time Complexity

• $O(n)$

size

std::uint32_t bv.size();

It returns $n$.

Constraints

• None

Time Complexity

• $O(1)$

get

std::uint32_t bv.get(std::uint32_t i);

It returns the $i$-th bit of the bit vector. (i.e., $0$ or $1$)

Constraints

• $0 \leq i < n$

Time Complexity

• $O(1)$

set

void bv.set(std::uint32_t i);

It updates the $i$-th bit of the bit vector to $1$.

Constraints

• $0 \leq i < n$

Time Complexity

• $O(1)$

build

void bv.build();

It builts the internal auxiliary data structure for the rank operation.

Constraints

• None

Time Complexity

• $O(n)$

zeros

std::uint32_t bv.zeros();

It returns the number of zero bits in the bit vector.

Constraints

• bv.build() has been called ever.
• bv.init() has not been called after the last call of bv.build().
• bv.set() has not been called after the last call of bv.build().

Time Complexity

• $O(1)$

rank0

std::uint32_t bv.rank0(std::uint32_t r);

It returns $|\{i \in \mathbb{N} \mid 0 \leq i < r \land \mathrm{bv.get}(i) = 0\}|$.

Constraints

• $0 \leq r \leq n$
• bv.build() has been called ever.
• bv.init() has not been called after the last call of bv.build().
• bv.set() has not been called after the last call of bv.build().

Time Complexity

• $O(1)$

rank1

std::uint32_t bv.rank1(std::uint32_t r);

It returns $|\{i \in \mathbb{N} \mid 0 \leq i < r \land \mathrm{bv.get}(i) = 1\}|$.

Constraints

• $0 \leq r \leq n$
• bv.build() has been called ever.
• bv.init() has not been called after the last call of bv.build().
• bv.set() has not been called after the last call of bv.build().

Time Complexity

• $O(1)$

Required by

• Range count distinct (tools/range_count_distinct.hpp)
• Wavelet matrix (tools/wavelet_matrix.hpp)

Verified with

• tests/range_count_distinct.test.cpp
• tests/wavelet_matrix/kth_smallest.test.cpp
• tests/wavelet_matrix/next_points.test.cpp
• tests/wavelet_matrix/prev_points.test.cpp
• tests/wavelet_matrix/range_freq.test.cpp
• tests/wavelet_matrix/range_prod.test.cpp

Code

#ifndef TOOLS_BIT_VECTOR_HPP
#define TOOLS_BIT_VECTOR_HPP

#include <cstdint>
#include <vector>
#include <immintrin.h>

// Source: https://nyaannyaan.github.io/library/data-structure-2d/wavelet-matrix.hpp.html
// License: CC0 1.0 Universal
// Author: Nyaan

namespace tools {
  class bit_vector {
  private:
    using u32 = ::std::uint32_t;
    using i64 = ::std::int64_t;
    using u64 = ::std::uint64_t;

    static constexpr u32 w = 64;
    ::std::vector<u64> m_block;
    ::std::vector<u32> m_count;
    u32 m_size, m_zeros;

  public:
    bit_vector() {}
    explicit bit_vector(int _n) { init(_n); }
    __attribute__((optimize("O3", "unroll-loops"))) void init(int _n) {
      m_size = m_zeros = _n;
      m_block.resize(m_size / w + 1, 0);
      m_count.resize(m_block.size(), 0);
    }

    u32 size() const { return m_size; }
    inline u32 get(u32 i) const { return u32(m_block[i / w] >> (i % w)) & 1u; }
    inline void set(u32 i) { m_block[i / w] |= 1LL << (i % w); }

    __attribute__((target("popcnt"))) void build() {
      for (u32 i = 1; i < m_block.size(); ++i)
        m_count[i] = m_count[i - 1] + _mm_popcnt_u64(m_block[i - 1]);
      m_zeros = rank0(m_size);
    }

    u32 zeros() const { return m_zeros; }
    inline u32 rank0(u32 i) const { return i - rank1(i); }
    __attribute__((target("bmi2,popcnt"))) inline u32 rank1(u32 i) const {
      return m_count[i / w] + _mm_popcnt_u64(_bzhi_u64(m_block[i / w], i % w));
    }
  };
}

#endif

#line 1 "tools/bit_vector.hpp"



#include <cstdint>
#include <vector>
#include <immintrin.h>

// Source: https://nyaannyaan.github.io/library/data-structure-2d/wavelet-matrix.hpp.html
// License: CC0 1.0 Universal
// Author: Nyaan

namespace tools {
  class bit_vector {
  private:
    using u32 = ::std::uint32_t;
    using i64 = ::std::int64_t;
    using u64 = ::std::uint64_t;

    static constexpr u32 w = 64;
    ::std::vector<u64> m_block;
    ::std::vector<u32> m_count;
    u32 m_size, m_zeros;

  public:
    bit_vector() {}
    explicit bit_vector(int _n) { init(_n); }
    __attribute__((optimize("O3", "unroll-loops"))) void init(int _n) {
      m_size = m_zeros = _n;
      m_block.resize(m_size / w + 1, 0);
      m_count.resize(m_block.size(), 0);
    }

    u32 size() const { return m_size; }
    inline u32 get(u32 i) const { return u32(m_block[i / w] >> (i % w)) & 1u; }
    inline void set(u32 i) { m_block[i / w] |= 1LL << (i % w); }

    __attribute__((target("popcnt"))) void build() {
      for (u32 i = 1; i < m_block.size(); ++i)
        m_count[i] = m_count[i - 1] + _mm_popcnt_u64(m_block[i - 1]);
      m_zeros = rank0(m_size);
    }

    u32 zeros() const { return m_zeros; }
    inline u32 rank0(u32 i) const { return i - rank1(i); }
    __attribute__((target("bmi2,popcnt"))) inline u32 rank1(u32 i) const {
      return m_count[i / w] + _mm_popcnt_u64(_bzhi_u64(m_block[i / w], i % w));
    }
  };
}

Back to top page