This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub toyama1710/cpp_library
#include "compact_data_structure/bit_vector.hpp"
#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; }; };