c ++中的位向量

Question

最近我听说过位向量,但我真的找不到任何关于这个主题的有用信息或教程.能否请您推荐一本关于如何实现自己的位向量类的书或快速教程？谢谢.

--- ///我无法回答我自己的问题,所以我决定编辑这篇文章.这就是我刚刚发现的:"游戏程序员的数据结构 - Ron Penton和Andre Lamothe".第4章,Bitvectors.本书详细解释了位向量,以及如何自己创建位向量类.玩得开心.

Answer 1

这是一个非常简单的静态大小的位向量实现。由于它依赖<cstdint>标头，因此它需要C ++ 11才能起作用，但是由于它基于C99功能，因此相当常见。在紧要关头，您可以使用C <stdint.h>标头，而只需在全局名称空间中使用类型。

注意：此内容是即时输入的，未经测试。我什至没有验证它是否可以编译。因此，可能存在错误。

#include <cstdint>  // ::std::uint64_t type
#include <cstddef> // ::std::size_t type
#include <algorithm>

class my_bitvector_base {
 protected:
   class bitref { // Prevent this class from being used anywhere else.
    public:
      bitref(::std::uint64_t &an_int, ::std::uint64_t mask)
           : an_int_(an_int), mask_(mask)
      {
      }

      const bitref &operator =(bool val) {
         if (val) {
            an_int_ |= mask_;
         } else {
            an_int_ &= ~mask_;
         }
         return *this;
      }
      const bitref &operator =(const bitref &br) {
         return this->operator =(bool(br));
      }
      operator bool() const {
         return ((an_int_ & mask_) != 0) ? true : false;
      }

    private:
      ::std::uint64_t &an_int_;
      ::std::uint64_t mask_;
   };
};

template < ::std::size_t Size >
class my_bitvector : public my_bitvector_base {
 private:
   static constexpr ::std::size_t numints = ((Size + 63) / 64);
 public:
   my_bitvector() { ::std::fill(array, array + numints, 0); }

   bool operator [](::std::size_t bitnum) const {
      const ::std::size_t bytenum = bit / 64;
      bitnum = bitnum % 64;
      return ((ints_[bytenum] & (::std::uint64_t(1) << bitnum)) != 0) ? true : false;
   }
   bitref operator[](::std::size_t bitnum) {
      const ::std::size_t bytenum = bit / 64;
      bitnum = bitnum % 64;
      ::std::uint64_t mask = ::std::uint64_t(1) << bitnum;
      return bitref(ints_[bytenum], mask);
   }

 private:
   ::std::uint64_t ints_[numints];
};

// Example uses
void test()
{
    my_bitvector<70> bits; // A 70 bit long bit vector initialized to all false
    bits[1] = true; // Set bit 1 to true
    bool abit = bits[1]; // abit should be true.
    abit = bits[69]; // abit should be false.
}

整个过程my_bitvector_base是创建一种私有类型。您可以在派生类的接口或实现中提及它，因为它是protected，但是您不能在其他上下文中提及它。这样可以防止人们存储的副本bitref。这一点很重要，因为bitref仅存在一个真正允许分配结果的方法，operator []因为就其全部智慧而言，C ++标准委员会尚未实现operator []=或分配数组元素的类似方法。

如您所见，位向量基本上是位数组。奇特的位向量将模拟所有初始化为true或false的“无限”位数组。他们通过跟踪已设置的最后一位及其之前的所有位来进行此操作。然后，如果您要求一点，它们只是返回初始化的值。

一个好的位向量也将实现operator &以及其他类似的优点，因此它们在参考位操作操作时的行为类似于一个非常大的无符号整数。