std::bitset的表现如何？
What is the performance of std::bitset?
我最近在 Programmers 上问了一个关于在 std::bitset 上使用原始类型的手动位操作的原因的问题。
从那次讨论中我得出结论，主要原因是它的性能相对较差，尽管我不知道这个观点有任何可衡量的基础。所以下一个问题是：
什么是性能损失，如果有的话，可能是通过使用std::bitset对基元的位操作造成的？
这个问题故意宽泛，因为网上查了下也没查到什么，所以就拿能查到的吧。基本上我在寻找一个资源，它提供了一些 std::bitset 与 'pre-bitset' 替代方案的分析，以解决一些使用 GCC、Clang and/or VC++ 的常见机器架构上的相同问题。有一篇非常全面的论文试图回答位向量的这个问题：
http://www.cs.up.ac.za/cs/vpieterse/pub/PieterseEtAl_SAICSIT2010.pdf
不幸的是，它早于或被认为超出范围 std::bitset，因此它专注于 vectors/dynamic 数组实现。
我真的只想知道 std::bitset 是否 比它打算解决的用例的替代方案更好。我已经知道它 更容易 和 更清晰 比整数上的位摆弄，但它是 fast?
更新
我 post 编辑这个已经很久了，但是：
I already know that it is easier and clearer than bit-fiddling on an
integer, but is it as fast?
如果您使用 bitset 的方式确实比位摆弄更清晰、更干净，例如一次检查一位而不是使用位掩码，那么您不可避免地会失去所有按位运算提供的那些好处，例如能够检查一次是否针对掩码设置了 64 位，或者使用 FFS 指令快速确定在 64 位中设置了哪一位。
我不确定 bitset 是否会以所有可能的方式使用（例如：使用它的按位 operator&），但如果你使用它 like 一个固定大小的布尔数组，这几乎是我经常看到人们使用它的方式，那么你通常会失去上面描述的所有这些好处。不幸的是，我们无法获得使用 operator[] 一次访问一位的那种表现力水平，并且让优化器计算出所有的按位操作以及 FFS 和 FFZ 等等，至少不是因为我最后一次检查（否则 bitset 将是我最喜欢的结构之一）。
现在，如果您打算将 bitset<N> bits 与 uint64_t bits[N/64] 互换使用，就像使用按位运算以相同的方式访问两者一样，它可能是同等的（自从这个古老的post)。但是你会失去许多使用 bitset 的好处。
for_each方法
我想，过去我遇到了一些误解，当我提出一个 for_each 方法来遍历 vector<bool>、deque 和 bitset 之类的东西时.这种方法的要点是利用容器的内部知识在调用仿函数时更有效地遍历元素，就像一些关联容器提供自己的 find 方法而不是使用 std::find比线性时间搜索更好。
例如，如果您通过使用 64 位掩码一次检查 64 个元素来了解这些容器的内部知识，则可以遍历 vector<bool> 或 bitset 的所有设置位当64个连续索引被占用时，同样使用FFS指令，当不是这种情况时。
但是在 operator++ 中必须执行此类标量逻辑的迭代器设计将不可避免地不得不做一些相当昂贵的事情，这只是在这些特殊情况下设计迭代器的性质。 bitset 完全缺少迭代器，这常常使人们希望使用它来避免处理按位逻辑，以使用 operator[] 在只想找出设置了哪些位的顺序循环中单独检查每个位。这也远不如 for_each 方法实现的效率。
Double/Nested 迭代器
上面提出的 for_each 容器特定方法的另一种替代方法是使用 double/nested 迭代器：即指向不同类型迭代器的子范围的外部迭代器.客户端代码示例：
for (auto outer_it = bitset.nbegin(); outer_it != bitset.nend(); ++outer_it)
{
for (auto inner_it = outer_it->first; inner_it != outer_it->last; ++inner_it)
// do something with *inner_it (bit index)
}
虽然不符合现在标准容器中可用的平面迭代器设计类型，但这可以允许进行一些非常有趣的优化。例如，想象这样的情况：
bitset<64> bits = 0x1fbf; // 0b1111110111111;
在这种情况下，外部迭代器可以通过几次按位迭代 ((FFZ/or/complement) 推断出要处理的第一个位范围是位 [0, 6]，此时我们可以通过 inner/nested 迭代器非常便宜地遍历该子范围（它只会增加一个整数，使 ++inner_it 等同于 ++int）。然后，当我们递增外部迭代器时，它可以非常快速地再次使用一些按位指令确定下一个范围是 [7, 13)。在我们遍历该子范围后，我们就完成了。再举个例子：
bitset<16> bits = 0xffff;
在这种情况下，第一个和最后一个子范围将是 [0, 16)，并且 bitset 可以使用单个按位指令来确定，此时我们可以遍历所有设置的位，然后我们'大功告成。
这种嵌套迭代器设计可以很好地映射到 vector<bool>、deque 和 bitset 以及人们可能创建的其他数据结构，例如展开的列表。
我说的不仅仅是纸上谈兵的猜测，因为我有一组类似于 deque 的数据结构，实际上与 vector 的顺序迭代相当（随机访问仍然明显较慢，特别是如果我们只是存储一堆原语并进行琐碎的处理）。但是，为了实现与 vector 相近的顺序迭代时间，我不得不使用这些类型的技术（for_each 方法和 double/nested 迭代器）来减少正在进行的处理和分支的数量在每次迭代中。否则我无法与时代竞争，否则仅使用平面迭代器设计 and/or operator[]。我当然不比标准库实现者聪明，但想出了一个类似 deque 的容器，它可以更快地顺序迭代，这强烈地向我暗示这是迭代器的标准接口设计的问题在这种情况下，在优化器无法优化的这些特殊情况下会带来一些开销。
旧答案
我是那些会给你类似性能答案的人之一，但我会尝试给你一些比 "just because" 更深入的东西。这是我通过实际分析和时间安排遇到的事情，而不仅仅是不信任和偏执。
bitset 和 vector<bool> 的最大问题之一是，如果您想像布尔数组一样使用它们，它们的界面设计“太方便了”。优化器非常擅长消除您为提供安全性、降低维护成本、减少更改侵入性等而建立的所有结构。他们在选择指令和分配最少数量的寄存器来制作此类代码方面做得特别好 运行与不太安全的 not-so-easy-to-maintain/change 替代品一样快。
以效率为代价使 bitset 接口“太方便”的部分是随机访问 operator[] 以及 vector<bool> 的迭代器设计。当您在索引 n 访问其中一个时，代码必须首先找出第 n 位属于哪个字节，然后是其中的位的子索引。第一阶段通常涉及针对左值的 division/rshifts 以及 modulo/bitwise，这比您尝试执行的实际位操作成本更高。
vector<bool> 的迭代器设计面临着类似的尴尬困境，它要么必须每迭代 8 次以上就分支到不同的代码中，要么支付上述那种索引成本。如果完成前者，它会使迭代之间的逻辑不对称，并且在极少数情况下，迭代器设计往往会影响性能。举个例子，如果 vector 有自己的 for_each 方法，你可以一次遍历 64 个元素的范围，只需将这些位屏蔽为 [=23] 的 64 位掩码=] 如果设置了所有位而不单独检查每个位。它甚至可以使用 FFS 一次性计算出范围。迭代器设计往往不可避免地必须以标量方式进行或存储更多状态，每次迭代都必须进行冗余检查。
对于随机访问，优化器似乎无法优化这种索引开销来确定在不需要时访问哪个字节和相关位（可能有点太 运行时间依赖），并且您往往会看到通过更多的手动代码处理位顺序获得显着的性能提升，并深入了解 byte/word/dword/qword 它正在处理的内容。这有点不公平，但是 std::bitset 的困难在于，在代码事先知道它想要访问哪个字节的情况下，没有办法进行公平比较，而且通常情况下，你倾向于提前获得此信息。在随机访问情况下，这是苹果与橙子的比较，但您通常只需要橙子。
如果界面设计涉及 bitset，其中 operator[] 返回代理，需要使用双索引访问模式，情况可能就不会如此。例如，在这种情况下，您可以通过使用模板参数写入 bitset[0][6] = true; bitset[0][7] = true; 来访问位 8，以指示代理的大小（例如 64 位）。一个好的优化器可能能够采用这样的设计，并通过将其转换为：bitset |= 0x60;
使其与手动进行位操作的老式手动方式相媲美
另一个可能有用的设计是 bitsets 提供了一种 for_each_bit 类型的方法，将位代理传递给您提供的仿函数。这实际上可能可以与手动方法相媲美。
std::deque也有类似的接口问题。它的性能不应该 比顺序访问 std::vector 慢很多。然而不幸的是，我们使用专为随机访问或通过迭代器设计的 operator[] 顺序访问它，并且 deques 的内部代表不能非常有效地映射到基于迭代器的设计。如果 deque 提供了自己的 for_each 种方法，那么它可能会开始更接近 std::vector's 顺序访问性能。这些是一些罕见的情况，在这些情况下，Sequence 接口设计会带来一些优化器通常无法消除的效率开销。好的优化器通常可以在生产构建中运行减少时间成本，但不幸的是，并非在所有情况下都如此。
对不起！
也很抱歉，回想起来，除了 bitset 之外，我在谈论 vector<bool> 和 deque 时，我还有些迷茫 post。这是因为我们有一个代码库，其中使用这三个，特别是迭代它们或使用它们进行随机访问，通常是热点。
苹果到橘子
正如旧答案中所强调的那样，将 bitset 的直接用法与具有低级按位逻辑的原始类型进行比较就像将苹果与橙子进行比较。 bitset 的实现效率并不高。如果您确实需要访问具有随机访问模式的一堆位，由于某种原因或其他原因，一次只需要检查和设置一个位，那么它可能是实现这种目的的理想选择。但我的观点是，我遇到的几乎所有用例都不需要这样做，而当不需要时，涉及按位运算的老式方法往往效率更高。
做了一个简短的测试分析 std::bitset 与 bool 数组的顺序和随机访问 - 你也可以：
#include <iostream>
#include <bitset>
#include <cstdlib> // rand
#include <ctime> // timer
inline unsigned long get_time_in_ms()
{
return (unsigned long)((double(clock()) / CLOCKS_PER_SEC) * 1000);
}
void one_sec_delay()
{
unsigned long end_time = get_time_in_ms() + 1000;
while(get_time_in_ms() < end_time)
{
}
}
int main(int argc, char **argv)
{
srand(get_time_in_ms());
using namespace std;
bitset<5000000> bits;
bool *bools = new bool[5000000];
unsigned long current_time, difference1, difference2;
double total;
one_sec_delay();
total = 0;
current_time = get_time_in_ms();
for (unsigned int num = 0; num != 200000000; ++num)
{
bools[rand() % 5000000] = rand() % 2;
}
difference1 = get_time_in_ms() - current_time;
current_time = get_time_in_ms();
for (unsigned int num2 = 0; num2 != 100; ++num2)
{
for (unsigned int num = 0; num != 5000000; ++num)
{
total += bools[num];
}
}
difference2 = get_time_in_ms() - current_time;
cout << "Bool:" << endl << "sum total = " << total << ", random access time = " << difference1 << ", sequential access time = " << difference2 << endl << endl;
one_sec_delay();
total = 0;
current_time = get_time_in_ms();
for (unsigned int num = 0; num != 200000000; ++num)
{
bits[rand() % 5000000] = rand() % 2;
}
difference1 = get_time_in_ms() - current_time;
current_time = get_time_in_ms();
for (unsigned int num2 = 0; num2 != 100; ++num2)
{
for (unsigned int num = 0; num != 5000000; ++num)
{
total += bits[num];
}
}
difference2 = get_time_in_ms() - current_time;
cout << "Bitset:" << endl << "sum total = " << total << ", random access time = " << difference1 << ", sequential access time = " << difference2 << endl << endl;
delete [] bools;
cin.get();
return 0;
}
请注意：总和的输出是必要的，因此编译器不会优化 for 循环 - 如果不使用循环的结果，有些人会这样做。
在具有以下标志的 GCC x64 下：-O2；-Wall；-march=native；-fomit-frame-pointer；-std=c++11；
我得到以下结果：
布尔数组：
随机访问时间 = 4695，顺序访问时间 = 390
比特集：
随机访问时间 = 5382，顺序访问时间 = 749
除了其他答案所说的关于访问性能的内容之外，还可能存在显着的 space 开销：典型的 bitset<> 实现仅使用最长的整数类型来支持其位。于是，下面的代码
#include <bitset>
#include <stdio.h>
struct Bitfield {
unsigned char a:1, b:1, c:1, d:1, e:1, f:1, g:1, h:1;
};
struct Bitset {
std::bitset<8> bits;
};
int main() {
printf("sizeof(Bitfield) = %zd\n", sizeof(Bitfield));
printf("sizeof(Bitset) = %zd\n", sizeof(Bitset));
printf("sizeof(std::bitset<1>) = %zd\n", sizeof(std::bitset<1>));
}
在我的机器上产生以下输出：
sizeof(Bitfield) = 1
sizeof(Bitset) = 8
sizeof(std::bitset<1>) = 8
如您所见，我的编译器分配了高达 64 位来存储单个位，使用位域方法，我只需要四舍五入到八位。
如果您有很多小的位集，space 用法中的因子八会变得很重要。
这里不是一个很好的答案，而是一个相关的轶事：
几年前我在研究实时软件，我们 运行 遇到了调度问题。有一个模块超出了时间预算，这非常令人惊讶，因为该模块只负责一些映射和 packing/unpacking 位 into/from 32 位字。
原来模块正在使用std::bitset。我们将其替换为手动操作，执行时间从 3 毫秒减少到 25 微秒。这是一个重大的性能问题和重大改进。
关键是，由此引起的性能问题 class 可能非常真实。
反问：为什么std::bitset写的那么没效率？
答：不是。
另一个反问：有什么区别：
std::bitset<128> a = src;
a[i] = true;
a = a << 64;
和
std::bitset<129> a = src;
a[i] = true;
a = a << 63;
答案：性能相差50倍http://quick-bench.com/iRokweQ6JqF2Il-T-9JSmR0bdyw
你需要非常小心你的要求，bitset支持很多东西，但每个都有自己的成本。通过正确处理，您将拥有与原始代码完全相同的行为：
void f(std::bitset<64>& b, int i)
{
b |= 1L << i;
b = b << 15;
}
void f(unsigned long& b, int i)
{
b |= 1L << i;
b = b << 15;
}
两者生成相同的程序集：https://godbolt.org/g/PUUUyd（64 位 GCC）
另一件事是 bitset 更适合 table 但这也有成本:
void h(std::bitset<64>& b, unsigned i)
{
b = b << i;
}
void h(unsigned long& b, unsigned i)
{
b = b << i;
}
如果 i > 64 则位设置将为零，在无符号的情况下我们有 UB。
void h(std::bitset<64>& b, unsigned i)
{
if (i < 64) b = b << i;
}
void h(unsigned long& b, unsigned i)
{
if (i < 64) b = b << i;
}
通过检查防止 UB 两者都生成相同的代码。
另一个地方是 set 和 []，第一个是安全的，意味着你永远不会得到 UB，但这会花费你一个分支。 [] 如果您使用错误的值，则有 UB 但与使用 var |= 1L<< i; 一样快。当然，如果 std::bitset 不需要比系统上可用的最大整数更多的位，因为否则你需要拆分值才能在内部 table 中获得正确的元素。这意味着 std::bitset<N> 大小 N 对性能非常重要。如果大于或小于最佳值，您将支付费用。
总的来说，我发现最好的方法是使用类似的东西：
constexpr size_t minBitSet = sizeof(std::bitset<1>)*8;
template<size_t N>
using fasterBitSet = std::bitset<minBitSet * ((N + minBitSet - 1) / minBitSet)>;
这将消除修剪超出位的成本：http://quick-bench.com/Di1tE0vyhFNQERvucAHLaOgucAY
我最近在 Programmers 上问了一个关于在 std::bitset 上使用原始类型的手动位操作的原因的问题。
从那次讨论中我得出结论，主要原因是它的性能相对较差，尽管我不知道这个观点有任何可衡量的基础。所以下一个问题是：
什么是性能损失，如果有的话，可能是通过使用std::bitset对基元的位操作造成的？
这个问题故意宽泛，因为网上查了下也没查到什么，所以就拿能查到的吧。基本上我在寻找一个资源，它提供了一些 std::bitset 与 'pre-bitset' 替代方案的分析，以解决一些使用 GCC、Clang and/or VC++ 的常见机器架构上的相同问题。有一篇非常全面的论文试图回答位向量的这个问题：
http://www.cs.up.ac.za/cs/vpieterse/pub/PieterseEtAl_SAICSIT2010.pdf
不幸的是，它早于或被认为超出范围 std::bitset，因此它专注于 vectors/dynamic 数组实现。
我真的只想知道 std::bitset 是否 比它打算解决的用例的替代方案更好。我已经知道它 更容易 和 更清晰 比整数上的位摆弄，但它是 fast?
更新
我 post 编辑这个已经很久了，但是：
I already know that it is easier and clearer than bit-fiddling on an integer, but is it as fast?
如果您使用 bitset 的方式确实比位摆弄更清晰、更干净，例如一次检查一位而不是使用位掩码，那么您不可避免地会失去所有按位运算提供的那些好处，例如能够检查一次是否针对掩码设置了 64 位，或者使用 FFS 指令快速确定在 64 位中设置了哪一位。
我不确定 bitset 是否会以所有可能的方式使用（例如：使用它的按位 operator&），但如果你使用它 like 一个固定大小的布尔数组，这几乎是我经常看到人们使用它的方式，那么你通常会失去上面描述的所有这些好处。不幸的是，我们无法获得使用 operator[] 一次访问一位的那种表现力水平，并且让优化器计算出所有的按位操作以及 FFS 和 FFZ 等等，至少不是因为我最后一次检查（否则 bitset 将是我最喜欢的结构之一）。
现在，如果您打算将 bitset<N> bits 与 uint64_t bits[N/64] 互换使用，就像使用按位运算以相同的方式访问两者一样，它可能是同等的（自从这个古老的post)。但是你会失去许多使用 bitset 的好处。
for_each方法
我想，过去我遇到了一些误解，当我提出一个 for_each 方法来遍历 vector<bool>、deque 和 bitset 之类的东西时.这种方法的要点是利用容器的内部知识在调用仿函数时更有效地遍历元素，就像一些关联容器提供自己的 find 方法而不是使用 std::find比线性时间搜索更好。
例如，如果您通过使用 64 位掩码一次检查 64 个元素来了解这些容器的内部知识，则可以遍历 vector<bool> 或 bitset 的所有设置位当64个连续索引被占用时，同样使用FFS指令，当不是这种情况时。
但是在 operator++ 中必须执行此类标量逻辑的迭代器设计将不可避免地不得不做一些相当昂贵的事情，这只是在这些特殊情况下设计迭代器的性质。 bitset 完全缺少迭代器，这常常使人们希望使用它来避免处理按位逻辑，以使用 operator[] 在只想找出设置了哪些位的顺序循环中单独检查每个位。这也远不如 for_each 方法实现的效率。
Double/Nested 迭代器
上面提出的 for_each 容器特定方法的另一种替代方法是使用 double/nested 迭代器：即指向不同类型迭代器的子范围的外部迭代器.客户端代码示例：
for (auto outer_it = bitset.nbegin(); outer_it != bitset.nend(); ++outer_it)
{
for (auto inner_it = outer_it->first; inner_it != outer_it->last; ++inner_it)
// do something with *inner_it (bit index)
}
虽然不符合现在标准容器中可用的平面迭代器设计类型，但这可以允许进行一些非常有趣的优化。例如，想象这样的情况：
bitset<64> bits = 0x1fbf; // 0b1111110111111;
在这种情况下，外部迭代器可以通过几次按位迭代 ((FFZ/or/complement) 推断出要处理的第一个位范围是位 [0, 6]，此时我们可以通过 inner/nested 迭代器非常便宜地遍历该子范围（它只会增加一个整数，使 ++inner_it 等同于 ++int）。然后，当我们递增外部迭代器时，它可以非常快速地再次使用一些按位指令确定下一个范围是 [7, 13)。在我们遍历该子范围后，我们就完成了。再举个例子：
bitset<16> bits = 0xffff;
在这种情况下，第一个和最后一个子范围将是 [0, 16)，并且 bitset 可以使用单个按位指令来确定，此时我们可以遍历所有设置的位，然后我们'大功告成。
这种嵌套迭代器设计可以很好地映射到 vector<bool>、deque 和 bitset 以及人们可能创建的其他数据结构，例如展开的列表。
我说的不仅仅是纸上谈兵的猜测，因为我有一组类似于 deque 的数据结构，实际上与 vector 的顺序迭代相当（随机访问仍然明显较慢，特别是如果我们只是存储一堆原语并进行琐碎的处理）。但是，为了实现与 vector 相近的顺序迭代时间，我不得不使用这些类型的技术（for_each 方法和 double/nested 迭代器）来减少正在进行的处理和分支的数量在每次迭代中。否则我无法与时代竞争，否则仅使用平面迭代器设计 and/or operator[]。我当然不比标准库实现者聪明，但想出了一个类似 deque 的容器，它可以更快地顺序迭代，这强烈地向我暗示这是迭代器的标准接口设计的问题在这种情况下，在优化器无法优化的这些特殊情况下会带来一些开销。
旧答案
我是那些会给你类似性能答案的人之一，但我会尝试给你一些比 "just because" 更深入的东西。这是我通过实际分析和时间安排遇到的事情，而不仅仅是不信任和偏执。
bitset 和 vector<bool> 的最大问题之一是，如果您想像布尔数组一样使用它们，它们的界面设计“太方便了”。优化器非常擅长消除您为提供安全性、降低维护成本、减少更改侵入性等而建立的所有结构。他们在选择指令和分配最少数量的寄存器来制作此类代码方面做得特别好 运行与不太安全的 not-so-easy-to-maintain/change 替代品一样快。
以效率为代价使 bitset 接口“太方便”的部分是随机访问 operator[] 以及 vector<bool> 的迭代器设计。当您在索引 n 访问其中一个时，代码必须首先找出第 n 位属于哪个字节，然后是其中的位的子索引。第一阶段通常涉及针对左值的 division/rshifts 以及 modulo/bitwise，这比您尝试执行的实际位操作成本更高。
vector<bool> 的迭代器设计面临着类似的尴尬困境，它要么必须每迭代 8 次以上就分支到不同的代码中，要么支付上述那种索引成本。如果完成前者，它会使迭代之间的逻辑不对称，并且在极少数情况下，迭代器设计往往会影响性能。举个例子，如果 vector 有自己的 for_each 方法，你可以一次遍历 64 个元素的范围，只需将这些位屏蔽为 [=23] 的 64 位掩码=] 如果设置了所有位而不单独检查每个位。它甚至可以使用 FFS 一次性计算出范围。迭代器设计往往不可避免地必须以标量方式进行或存储更多状态，每次迭代都必须进行冗余检查。
对于随机访问，优化器似乎无法优化这种索引开销来确定在不需要时访问哪个字节和相关位（可能有点太 运行时间依赖），并且您往往会看到通过更多的手动代码处理位顺序获得显着的性能提升，并深入了解 byte/word/dword/qword 它正在处理的内容。这有点不公平，但是 std::bitset 的困难在于，在代码事先知道它想要访问哪个字节的情况下，没有办法进行公平比较，而且通常情况下，你倾向于提前获得此信息。在随机访问情况下，这是苹果与橙子的比较，但您通常只需要橙子。
如果界面设计涉及 bitset，其中 operator[] 返回代理，需要使用双索引访问模式，情况可能就不会如此。例如，在这种情况下，您可以通过使用模板参数写入 bitset[0][6] = true; bitset[0][7] = true; 来访问位 8，以指示代理的大小（例如 64 位）。一个好的优化器可能能够采用这样的设计，并通过将其转换为：bitset |= 0x60;
另一个可能有用的设计是 bitsets 提供了一种 for_each_bit 类型的方法，将位代理传递给您提供的仿函数。这实际上可能可以与手动方法相媲美。
std::deque也有类似的接口问题。它的性能不应该 比顺序访问 std::vector 慢很多。然而不幸的是，我们使用专为随机访问或通过迭代器设计的 operator[] 顺序访问它，并且 deques 的内部代表不能非常有效地映射到基于迭代器的设计。如果 deque 提供了自己的 for_each 种方法，那么它可能会开始更接近 std::vector's 顺序访问性能。这些是一些罕见的情况，在这些情况下，Sequence 接口设计会带来一些优化器通常无法消除的效率开销。好的优化器通常可以在生产构建中运行减少时间成本，但不幸的是，并非在所有情况下都如此。
对不起！
也很抱歉，回想起来，除了 bitset 之外，我在谈论 vector<bool> 和 deque 时，我还有些迷茫 post。这是因为我们有一个代码库，其中使用这三个，特别是迭代它们或使用它们进行随机访问，通常是热点。
苹果到橘子
正如旧答案中所强调的那样，将 bitset 的直接用法与具有低级按位逻辑的原始类型进行比较就像将苹果与橙子进行比较。 bitset 的实现效率并不高。如果您确实需要访问具有随机访问模式的一堆位，由于某种原因或其他原因，一次只需要检查和设置一个位，那么它可能是实现这种目的的理想选择。但我的观点是，我遇到的几乎所有用例都不需要这样做，而当不需要时，涉及按位运算的老式方法往往效率更高。
做了一个简短的测试分析 std::bitset 与 bool 数组的顺序和随机访问 - 你也可以：
#include <iostream>
#include <bitset>
#include <cstdlib> // rand
#include <ctime> // timer
inline unsigned long get_time_in_ms()
{
return (unsigned long)((double(clock()) / CLOCKS_PER_SEC) * 1000);
}
void one_sec_delay()
{
unsigned long end_time = get_time_in_ms() + 1000;
while(get_time_in_ms() < end_time)
{
}
}
int main(int argc, char **argv)
{
srand(get_time_in_ms());
using namespace std;
bitset<5000000> bits;
bool *bools = new bool[5000000];
unsigned long current_time, difference1, difference2;
double total;
one_sec_delay();
total = 0;
current_time = get_time_in_ms();
for (unsigned int num = 0; num != 200000000; ++num)
{
bools[rand() % 5000000] = rand() % 2;
}
difference1 = get_time_in_ms() - current_time;
current_time = get_time_in_ms();
for (unsigned int num2 = 0; num2 != 100; ++num2)
{
for (unsigned int num = 0; num != 5000000; ++num)
{
total += bools[num];
}
}
difference2 = get_time_in_ms() - current_time;
cout << "Bool:" << endl << "sum total = " << total << ", random access time = " << difference1 << ", sequential access time = " << difference2 << endl << endl;
one_sec_delay();
total = 0;
current_time = get_time_in_ms();
for (unsigned int num = 0; num != 200000000; ++num)
{
bits[rand() % 5000000] = rand() % 2;
}
difference1 = get_time_in_ms() - current_time;
current_time = get_time_in_ms();
for (unsigned int num2 = 0; num2 != 100; ++num2)
{
for (unsigned int num = 0; num != 5000000; ++num)
{
total += bits[num];
}
}
difference2 = get_time_in_ms() - current_time;
cout << "Bitset:" << endl << "sum total = " << total << ", random access time = " << difference1 << ", sequential access time = " << difference2 << endl << endl;
delete [] bools;
cin.get();
return 0;
}
请注意：总和的输出是必要的，因此编译器不会优化 for 循环 - 如果不使用循环的结果，有些人会这样做。
在具有以下标志的 GCC x64 下：-O2；-Wall；-march=native；-fomit-frame-pointer；-std=c++11； 我得到以下结果：
布尔数组： 随机访问时间 = 4695，顺序访问时间 = 390
比特集： 随机访问时间 = 5382，顺序访问时间 = 749
除了其他答案所说的关于访问性能的内容之外，还可能存在显着的 space 开销：典型的 bitset<> 实现仅使用最长的整数类型来支持其位。于是，下面的代码
#include <bitset>
#include <stdio.h>
struct Bitfield {
unsigned char a:1, b:1, c:1, d:1, e:1, f:1, g:1, h:1;
};
struct Bitset {
std::bitset<8> bits;
};
int main() {
printf("sizeof(Bitfield) = %zd\n", sizeof(Bitfield));
printf("sizeof(Bitset) = %zd\n", sizeof(Bitset));
printf("sizeof(std::bitset<1>) = %zd\n", sizeof(std::bitset<1>));
}
在我的机器上产生以下输出：
sizeof(Bitfield) = 1
sizeof(Bitset) = 8
sizeof(std::bitset<1>) = 8
如您所见，我的编译器分配了高达 64 位来存储单个位，使用位域方法，我只需要四舍五入到八位。
如果您有很多小的位集，space 用法中的因子八会变得很重要。
这里不是一个很好的答案，而是一个相关的轶事：
几年前我在研究实时软件，我们 运行 遇到了调度问题。有一个模块超出了时间预算，这非常令人惊讶，因为该模块只负责一些映射和 packing/unpacking 位 into/from 32 位字。
原来模块正在使用std::bitset。我们将其替换为手动操作，执行时间从 3 毫秒减少到 25 微秒。这是一个重大的性能问题和重大改进。
关键是，由此引起的性能问题 class 可能非常真实。
反问：为什么std::bitset写的那么没效率？
答：不是。
另一个反问：有什么区别：
std::bitset<128> a = src;
a[i] = true;
a = a << 64;
和
std::bitset<129> a = src;
a[i] = true;
a = a << 63;
答案：性能相差50倍http://quick-bench.com/iRokweQ6JqF2Il-T-9JSmR0bdyw
你需要非常小心你的要求，bitset支持很多东西，但每个都有自己的成本。通过正确处理，您将拥有与原始代码完全相同的行为：
void f(std::bitset<64>& b, int i)
{
b |= 1L << i;
b = b << 15;
}
void f(unsigned long& b, int i)
{
b |= 1L << i;
b = b << 15;
}
两者生成相同的程序集：https://godbolt.org/g/PUUUyd（64 位 GCC）
另一件事是 bitset 更适合 table 但这也有成本:
void h(std::bitset<64>& b, unsigned i)
{
b = b << i;
}
void h(unsigned long& b, unsigned i)
{
b = b << i;
}
如果 i > 64 则位设置将为零，在无符号的情况下我们有 UB。
void h(std::bitset<64>& b, unsigned i)
{
if (i < 64) b = b << i;
}
void h(unsigned long& b, unsigned i)
{
if (i < 64) b = b << i;
}
通过检查防止 UB 两者都生成相同的代码。
另一个地方是 set 和 []，第一个是安全的，意味着你永远不会得到 UB，但这会花费你一个分支。 [] 如果您使用错误的值，则有 UB 但与使用 var |= 1L<< i; 一样快。当然，如果 std::bitset 不需要比系统上可用的最大整数更多的位，因为否则你需要拆分值才能在内部 table 中获得正确的元素。这意味着 std::bitset<N> 大小 N 对性能非常重要。如果大于或小于最佳值，您将支付费用。
总的来说，我发现最好的方法是使用类似的东西：
constexpr size_t minBitSet = sizeof(std::bitset<1>)*8;
template<size_t N>
using fasterBitSet = std::bitset<minBitSet * ((N + minBitSet - 1) / minBitSet)>;
这将消除修剪超出位的成本：http://quick-bench.com/Di1tE0vyhFNQERvucAHLaOgucAY