利用位運算節省 bool 數組內存佔用
由於布爾值在內存中只需要一個 bit 位就可以表示和計算，而 bool 類型和 integer 類型都會佔用遠大於 1 個 bit 的空間，所以，使用 bool 或 integer 作為基礎類型來存儲布爾連續向量，是缺乏內存效率意識的設計。
高效的設計為：借鑑 bloom filter 的思想，利用連續的 byte 來存儲以 8 個布爾值為段的數組。這樣就能將內存使用優化為本來（假設原先使用 char 來表示單個布爾）的 1/8。
class BitBoolArray {
public:
explicit BitBoolArray(size_t n)
: cap_((assert(n > 0), n)),
arr_(std::make_unique<uint8_t[]>((cap_ - 1) / 8 + 1)) {}
virtual ~BitBoolArray() = default;
bool get(size_t idx) const {
assert(idx < cap_);
if ((arr_[idx / 8] & (1u << (idx % 8))) == 0) {
return false;
}
return true;
}
void set(size_t idx, bool val) {
assert(idx < cap_);
if (val) {
arr_[idx / 8] |= (1u << (idx % 8));
return;
}
arr_[idx / 8] &= ~(1u << (idx % 8));
}
size_t size() const { return cap_; }
private:
size_t cap_;
std::unique_ptr<uint8_t[]> arr_;
};
