相关资料：
C++实现BitMap数据结构
c++ bitset类用法
libgrape-lite/grape/utils/bitset.h
libgrape-lite/grape/utils/vertex_set.h

个人理解：因为bitset就是利用每个位来表示一个数是否存在(0/1)，所以本质上bitset就类似于vector<bool>，只是bitset在存储和效率方面可能有优势。然后bitset用来做set的思想还是和数组一样，只是每个数的每一bit表示一个数，例如3个64位的整数，在bitset中表示：0~63 64~127 ``128~191。所以用三个64位整数可以表示：3*64个数了。

demo:
包含两个文件，一个时测试文件，一个是阿里开源项目中对bitset封装的类。
文件1：test.cc

#include <iostream>
#include "../utils/bitset.h"

using Bitset = grape::Bitset;

void print_bitset(Bitset &bs, int begin, int end){
    std::cout << "----------------" << std::endl;
    for(int batch = begin; batch < end; batch+=64){
        int v = batch;
        std::cout << "batch=" << batch << std::endl;
        uint64_t word = bs.get_word(batch-begin); // 获得数组中的一个元素，每个元素64位，每位表示一个元素
        while (word != 0) {
            if (word & 1) {
                std::cout << v << "\n";
            }
            ++v;
            word = word >> 1;
        }
    }
}

int main(){

    int begin = 70;
    int end = 128;

    Bitset bs;
    bs.init(end-begin);

    // 指定位置设置为1
    bs.set_bit(72 - begin);
    bs.set_bit(80 - begin);
    bs.set_bit(70 - begin);
    bs.set_bit(100 - begin);
    // 重置为0
    bs.reset_bit(72 - begin);
    
    print_bitset(bs, begin, end);
    std::cout << "bs.count=" << bs.count() << std::endl;

    Bitset bs2;
    bs2.init(end-begin);
    bs2.set_bit(84 - begin);
    print_bitset(bs2, begin, end);
    std::cout << "bs2.count=" << bs2.count() << std::endl;

    bs.parallel_clear(4); // 四个线程并行清理
    bs.swap(bs2); // 交换两个bitset的内容

    print_bitset(bs, begin, end);
    std::cout << "bs.count=" << bs.count() << std::endl;

    print_bitset(bs2, begin, end);
    std::cout << "bs2.count=" << bs2.count() << std::endl;

    return 0;
}

运行命令及结果：

g++ test.cc && ./a.out 
----------------
batch=70
70
80
100
bs.count=3
----------------
batch=70
84
bs2.count=1
----------------
batch=70
84
bs.count=1
----------------
batch=70
bs2.count=0

文件2：bitset.h

/** Copyright 2020 Alibaba Group Holding Limited.

Licensed under the Apache License, Version 2.0 (the "License");
you may not use this file except in compliance with the License.
You may obtain a copy of the License at

    http://www.apache.org/licenses/LICENSE-2.0

Unless required by applicable law or agreed to in writing, software
distributed under the License is distributed on an "AS IS" BASIS,
WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
See the License for the specific language governing permissions and
limitations under the License.
*/

#ifndef UTILS_BITSET_H_
#define UTILS_BITSET_H_

#include <stdlib.h>

#include <algorithm>
#include <utility>

#define WORD_SIZE(n) (((n) + 63ul) >> 6)

#define WORD_INDEX(i) ((i) >> 6)
#define BIT_OFFSET(i) ((i) &0x3f)

#define ROUND_UP(i) (((i) + 63ul) & (~63ul))
#define ROUND_DOWN(i) ((i) & (~63ul))

namespace grape {

/**
 * @brief Bitset is a highly-optimized bitset implementation.
 */
class Bitset {
 public:
  Bitset() : data_(NULL), size_(0), size_in_words_(0) {}
  explicit Bitset(size_t size) : size_(size) {
    size_in_words_ = WORD_SIZE(size_);
    data_ = static_cast<uint64_t*>(malloc(size_in_words_ * sizeof(uint64_t)));
    clear();
  }
  ~Bitset() {
    if (data_ != NULL) {
      free(data_);
    }
  }

  void init(size_t size) {
    if (data_ != NULL) {
      free(data_);
    }
    size_ = size;
    size_in_words_ = WORD_SIZE(size_);
    data_ = static_cast<uint64_t*>(malloc(size_in_words_ * sizeof(uint64_t)));
    clear();
  }

  void clear() {
    for (size_t i = 0; i < size_in_words_; ++i) {
      data_[i] = 0;
    }
  }

  void parallel_clear(int thread_num) {
#pragma omp parallel for num_threads(thread_num)
    for (size_t i = 0; i < size_in_words_; ++i) {
      data_[i] = 0;
    }
  }

  bool empty() const {
    for (size_t i = 0; i < size_in_words_; ++i) {
      if (data_[i]) {
        return false;
      }
    }
    return true;
  }

  bool partial_empty(size_t begin, size_t end) const {
    end = std::min(end, size_);
    size_t cont_beg = ROUND_UP(begin);
    size_t cont_end = ROUND_DOWN(end);
    size_t word_beg = WORD_INDEX(cont_beg);
    size_t word_end = WORD_INDEX(cont_end);
    for (size_t i = word_beg; i < word_end; ++i) {
      if (data_[i]) {
        return false;
      }
    }
    if (cont_beg != begin) {
      uint64_t first_word = data_[WORD_INDEX(begin)];
      first_word = (first_word >> (64 - (cont_beg - begin)));
      if (first_word) {
        return false;
      }
    }
    if (cont_end != end) {
      uint64_t last_word = data_[WORD_INDEX(end)];
      last_word = (last_word & ((1ul << (end - cont_end)) - 1));
      if (last_word) {
        return false;
      }
    }
    return true;
  }

  bool get_bit(size_t i) const {
    return data_[WORD_INDEX(i)] & (1ul << BIT_OFFSET(i));
  }

  void set_bit(size_t i) {
    __sync_fetch_and_or(data_ + WORD_INDEX(i), 1ul << BIT_OFFSET(i));
  }

  bool set_bit_with_ret(size_t i) {
    uint64_t mask = 1ul << BIT_OFFSET(i);
    uint64_t ret = __sync_fetch_and_or(data_ + WORD_INDEX(i), mask);
    return !(ret & mask);
  }

  void reset_bit(size_t i) {
    __sync_fetch_and_and(data_ + WORD_INDEX(i), ~(1ul << BIT_OFFSET(i)));
  }

  bool reset_bit_with_ret(size_t i) {
    uint64_t mask = 1ul << BIT_OFFSET(i);
    uint64_t ret = __sync_fetch_and_and(data_ + WORD_INDEX(i), ~mask);
    return (ret & mask);
  }

  void swap(Bitset& other) {
    std::swap(size_, other.size_);
    std::swap(data_, other.data_);
    std::swap(size_in_words_, other.size_in_words_);
  }

  size_t count() const {
    size_t ret = 0;
    for (size_t i = 0; i < size_in_words_; ++i) {
      ret += __builtin_popcountll(data_[i]);
    }
    return ret;
  }

  size_t parallel_count(int thread_num) const {
    size_t ret = 0;
#pragma omp parallel for num_threads(thread_num) reduction(+ : ret)
    for (size_t i = 0; i < size_in_words_; ++i) {
      ret += __builtin_popcountll(data_[i]);
    }
    return ret;
  }

  size_t partial_count(size_t begin, size_t end) const {
    size_t ret = 0;
    size_t cont_beg = ROUND_UP(begin);
    size_t cont_end = ROUND_DOWN(end);
    size_t word_beg = WORD_INDEX(cont_beg);
    size_t word_end = WORD_INDEX(cont_end);
    for (size_t i = word_beg; i < word_end; ++i) {
      ret += __builtin_popcountll(data_[i]);
    }
    if (cont_beg != begin) {
      uint64_t first_word = data_[WORD_INDEX(begin)];
      first_word = (first_word >> (64 - (cont_beg - begin)));
      ret += __builtin_popcountll(first_word);
    }
    if (cont_end != end) {
      uint64_t last_word = data_[WORD_INDEX(end)];
      last_word = (last_word & ((1ul << (end - cont_end)) - 1));
      ret += __builtin_popcountll(last_word);
    }
    return ret;
  }

  size_t parallel_partial_count(int thread_num, size_t begin,
                                size_t end) const {
    size_t ret = 0;
    size_t cont_beg = ROUND_UP(begin);
    size_t cont_end = ROUND_DOWN(end);
    size_t word_beg = WORD_INDEX(cont_beg);
    size_t word_end = WORD_INDEX(cont_end);
#pragma omp parallel for num_threads(thread_num) reduction(+ : ret)
    for (size_t i = word_beg; i < word_end; ++i) {
      ret += __builtin_popcountll(data_[i]);
    }
    if (cont_beg != begin) {
      uint64_t first_word = data_[WORD_INDEX(begin)];
      first_word = (first_word >> (64 - (cont_beg - begin)));
      ret += __builtin_popcountll(first_word);
    }
    if (cont_end != end) {
      uint64_t last_word = data_[WORD_INDEX(end)];
      last_word = (last_word & ((1ul << (end - cont_end)) - 1));
      ret += __builtin_popcountll(last_word);
    }
    return ret;
  }

  inline uint64_t get_word(size_t i) const { return data_[WORD_INDEX(i)]; }

  inline const uint64_t* get_word_ptr(size_t i) const {
    return &data_[WORD_INDEX(i)];
  }

 private:
  uint64_t* data_;
  size_t size_;
  size_t size_in_words_;
};

class RefBitset {
 public:
  RefBitset() : data(NULL) {}
  RefBitset(void* d, size_t b, size_t e) {
    data = static_cast<uint64_t*>(d);
    begin = b / 64 * 64;
    end = (e + 63) / 64 * 64;

    data[0] &= (~((1ul << (b - begin)) - 1ul));
    data[((end - begin) / 64) - 1] &= ((1ul << (64 - (end - e))) - 1ul);
  }
  ~RefBitset() {}

  bool get_bit(size_t loc) const {
    return data[WORD_INDEX(loc - begin)] & (1ul << BIT_OFFSET(loc));
  }

  uint64_t get_word_by_index(size_t index) { return data[index]; }

  size_t get_word_num() const { return (end - begin) / 64; }

  uint64_t* data;
  size_t begin;
  size_t end;
};

#undef WORD_SIZE
#undef WORD_INDEX
#undef BIT_OFFSET
#undef ROUND_UP
#undef ROUND_DOWN

}  // namespace grape

#endif  // UTILS_BITSET_H_