C++中的位向量
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/8565674/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
bit vectors in c++
提问by Vis Viva
Recently I heard about bit vectors, but i cant really find any useful info or tutorials on this topic. Can you please suggest a book or a quick tutorial on how to implement your own bit vector classes? Thank you.
最近我听说了位向量，但我真的找不到关于这个主题的任何有用的信息或教程。你能推荐一本书或一个关于如何实现你自己的位向量类的快速教程吗？谢谢你。
---/// i cant post answers to my own questions, so i decided to edit this post. here is what i have just found: "Data Structure for Game Programmers - Ron Penton and Andre Lamothe". Chapter 4, Bitvectors. This book has thorough explanation of bit vectors, and how to make a bit vector class yourself. have fun.
---//// 我不能发布我自己问题的答案，所以我决定编辑这篇文章。这是我刚刚发现的内容：“游戏程序员的数据结构 - Ron Penton 和 Andre Lamothe”。第 4 章，位向量。这本书对位向量有详尽的解释，以及如何自己制作位向量类。玩得开心。
采纳答案by Omnifarious
Here is a very simple statically sized bit vector implementation. It requires C++11 to function since it relies on the <cstdint>header, but this header is fairly commonly found since it's based on a C99 feature. In a pinch you can use the C <stdint.h>header and simply use types in the global namespace instead.
这是一个非常简单的静态大小的位向量实现。它需要 C++11 才能运行，因为它依赖于<cstdint>头文件，但是这个头文件很常见，因为它基于 C99 特性。在紧要关头，您可以使用 C<stdint.h>头文件，而只需使用全局命名空间中的类型。
Note:This was typed on-the-fly and isn't tested at all. I didn't even verify it would compile. So, there may be errors.
注意：这是即时输入的，根本没有经过测试。我什至没有验证它会编译。所以，可能会出现错误。
#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.
}
The whole my_bitvector_basething is to create a sort of private type. You can mention it in the interface or implementation for derived classes because it's protected, but you can't mention it other contexts. This prevents people from storing a copy of a bitref. This is important because a bitrefonly really exists to allow assignment to the result of operator []because the C++ standards committee, in all their wisdom, has not implemented operator []=or something similar for assigning to an array element.
整个过程my_bitvector_base是创建一种私有类型。您可以在派生类的接口或实现中提及它，因为它是protected，但您不能在其他上下文中提及它。这可以防止人们存储bitref. 这很重要，因为bitref只有真正存在才允许对结果进行赋值，operator []因为 C++ 标准委员会以其所有智慧尚未实现operator []=或类似的东西来分配给数组元素。
As you can see, a bit vector is basically an array of bits. Fancier bit vectors will simulate an 'infinite' array of bits all initialized to true or false. They do this by tracking the very last bit that has been set and all bits before it. And if you ask for a bit after that, they just return the initialized value.
如您所见，位向量基本上是位数组。更高级的位向量将模拟所有初始化为真或假的“无限”位数组。他们通过跟踪已设置的最后一位及其之前的所有位来做到这一点。如果您在那之后要求一点，他们只会返回初始化值。
A good bit vector will also implement operator &and other such niceties so they behave sort of like a very large unsigned integer with reference to bit manipulation operations.
一个好的位向量也将实现operator &和其他这样的细节，所以它们的行为有点像一个非常大的无符号整数，参考位操作操作。
回答by Totonga
vector<bool> is a specialization of the vector template. A normal bool variable requires at least one byte, but since a bool only has two states the ideal implementation of vector is such that each bool value only requires one bit. This means the iterator must be specially-defined, and cannot be a bool*.
vector< bool> 是矢量模板的特化。一个普通的 bool 变量至少需要一个字节，但是因为一个 bool 只有两个状态，所以 vector 的理想实现是每个 bool 值只需要一个位。这意味着迭代器必须是专门定义的，不能是 bool*。
from Thinking CPP Vol-2 from Bruce Eckel chapter 4: STL Containers & Iterators
来自 Bruce Eckel 的 Thinking CPP Vol-2 第 4 章：STL 容器和迭代器
The book can be downloaded for free at http://www.mindviewinc.com/Books/downloads.htmland it contains more informations on bits and C++
该书可在http://www.mindviewinc.com/Books/downloads.html免费下载 ，其中包含有关位和 C++ 的更多信息
