我最近问了一个关于Programmers的问题，关于在std::bitset上使用原始类型的手动位操作的原因。
从这个讨论中我得出结论，主要原因是它的表现相对较差，尽管我不知道这种观点有任何可靠的依据。接下来的问题是：
使用std::bitset对基元的位操作可能会产生什么样的性能影响？
这个问题有意广泛，因为在网上看后我找不到任何东西，所以我会拿走我能得到的东西。基本上我是在使用GCC，Clang和/或VC ++在一些常见的机器架构上提供std::bitset与'pre-bitset'替代相同问题的资源之后。有一篇非常全面的论文试图回答这个问题的位向量：
http://www.cs.up.ac.za/cs/vpieterse/pub/PieterseEtAl_SAICSIT2010.pdf
不幸的是，它要么早于或考虑超出范围std::bitset，所以它专注于向量/动态数组实现。
我真的只是想知道std::bitset是否比它想要解决的用例更好。我已经知道它比一个整数上的比特更容易和更清晰，但它是否同样快？
更新
我发布这篇文章已经很久了，但是：
我已经知道它比一个整数上的比特更容易和更清晰，但它是否同样快？
如果你使用bitset的方式实际上使它比bit-fiddling更清晰，更清晰，比如一次检查一个位而不是使用位掩码，那么你不可避免地会失去按位操作提供的所有好处，比如能够检查是否一次针对掩码设置了64位，或者使用FFS指令快速确定在64位中设置了哪个位。
我不确定bitset会以各种可能的方式使用惩罚（例如：使用它的按位operator&），但如果你像固定大小的布尔数组一样使用它，这几乎就是我总是看到人们使用它的方式，那么你通常会失去上述所有这些好处。遗憾的是，我们无法获得只使用operator[]一次访问一位的表达能力，并让优化器找出所有的按位操作，FFS和FFZ等等为我们继续，至少从上次开始我没有检查（否则bitset将是我最喜欢的结构之一）。
现在，如果你打算像bitset<N> bits那样交替使用uint64_t bits[N/64]，就像在使用按位操作一样访问它们时，它可能是平价的（自从这个古老的帖子以来没有检查过）。但是，你首先失去了使用bitset的许多好处。
for_each方法
在我过去，当我提出for_each方法来迭代vector<bool>，deque和bitset之类的东西时，我想到了一些误解。这种方法的关键是利用容器的内部知识在调用仿函数时更有效地迭代元素，就像一些关联容器提供自己的find方法而不是使用std::find做一个比线性时间更好的方法搜索。
例如，如果您通过在占用64个连续索引时使用64位掩码一次检查64个元素来了解这些容器的内部知识，则可以迭代vector<bool>或bitset的所有设置位，并且同样在使用FFS指令时事实并非如此。
但是，必须在operator++中执行这种类型的标量逻辑的迭代器设计将不可避免地需要做一些相当昂贵的事情，仅仅是在这些特殊情况下设计迭代器的本质。 bitset完全没有迭代器，这通常会让人们想要使用它来避免处理按位逻辑，使用operator[]在顺序循环中单独检查每个位，只是想找出哪些位被设置。这也不像for_each方法实现那样有效。
双/嵌套迭代器
上面提出的for_each容器特定方法的另一种替代方法是使用双/嵌套迭代器：即外部迭代器，它指向不同类型迭代器的子范围。客户端代码示例：
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 /或/补码）推断出要处理的第一个位范围是位[0,6]，此时我们可以迭代通过内部/嵌套迭代器非常便宜地子范围（它只会增加一个整数，使得++inner_it等同于++int）。然后当我们递增外部迭代器时，它可以非常快速地再次使用一些按位指令确定下一个范围是[7,13]。在我们遍历该子范围之后，我们就完成了。以此为另一个例子：
bitset<16> bits = 0xffff;
在这种情况下，第一个和最后一个子范围将是[0, 16)，并且bitset可以确定使用单个按位指令，此时我们可以迭代所有设置位然后我们就完成了。
这种类型的嵌套迭代器设计可以很好地映射到vector<bool>，deque和bitset以及人们可能创建的其他数据结构，如展开列表。
我说的方式不仅仅是扶手椅的推测，因为我有一组类似于deque的数据结构，它实际上与vector的顺序迭代相同（对于随机访问来说仍然明显较慢，特别是如果我们'只是存储一堆原语并进行简单的处理）。但是，为了实现vector顺序迭代的可比时间，我必须使用这些类型的技术（for_each方法和双/嵌套迭代器）来减少每次迭代中正在进行的处理和分支的数量。我只能使用平面迭代器设计和/或operator[]，无法与时俱进。而且我当然不比标准库实现者更聪明，但想出了一个类似deque的容器，它可以更快地顺序迭代，这强烈告诉我，在这种情况下，迭代器的标准接口设计是一个问题，在这些奇怪的情况下，优化器无法优化掉一些开销。
老答案
我是那些会给你类似性能答案的人之一，但我会尝试给你一些比"just because"更深入的东西。这是我通过实际剖析和计时而遇到的，而不仅仅是不信任和偏执。
bitset和vector<bool>最大的问题之一是它们的界面设计“太方便”了，如果你想像一系列布尔一样使用它们。优化器可以很好地消除您建立的所有结构，从而提供安全性，降低维护成本，减少更改的干扰等。通过选择指令并分配最少数量的寄存器，使这些代码运行速度与不那么安全，不那么容易维护/改变替代品。
以效率为代价使bitset接口“太方便”的部分是随机访问operator[]以及vector<bool>的迭代器设计。当您在索引n访问其中一个时，代码必须首先确定第n位属于哪个字节，然后是该索引中的位的子索引。第一阶段通常涉及对lvalue的分割/缩减以及模/按位，并且比您尝试执行的实际位操作更昂贵。
vector<bool>的迭代器设计面临着类似的尴尬困境，它要么必须每次迭代8次以上分支到不同的代码，要么支付上述的索引成本。如果前者完成，它会使迭代中的逻辑不对称，并且迭代器设计往往会在极少数情况下受到性能影响。举例来说，如果vector有自己的for_each方法，你可以通过仅针对vector<bool>的64位掩码屏蔽位来同时迭代一系列64个元素，如果所有位都设置而不检查每个位个别。它甚至可以使用FFS同时计算出范围。迭代器设计往往不得不以标量方式进行，或者存储更多状态，每次迭代都必须对其进行冗余检查。
对于随机访问，优化器似乎无法优化此索引开销，以确定在不需要时访问哪个字节和相对位（可能有点过于依赖于运行时），并且您倾向于看到显着的性能提升手动编码处理位，并具有对其正在处理的字节/字/双字/ 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的内部rep不能非常有效地映射到基于迭代器的设计。如果deque提供了自己的for_each方法，那么它可能会开始更接近std::vector's顺序访问性能。这些是一些罕见的情况，其中Sequence接口设计带来了优化器通常无法消除的一些效率开销。通常，优秀的优化器可以在生产构建中节省运行时的成本，但遗憾的是并非在所有情况下都如此。
抱歉!
也很遗憾，回想起来，我在这篇文章中闲聊了一下vector<bool>和deque以及bitset。这是因为我们有一个代码库，使用这三个代码库，特别是通过它们进行迭代或使用随机访问，通常是热点。
苹果到橘子
正如旧答案所强调的那样，将bitset的简单用法与低级按位逻辑的原始类型进行比较，就是将苹果与橙子进行比较。它不像bitset实现它的效率非常低效。如果你真的需要访问具有随机访问模式的一堆比特，由于某种原因，由于某种原因需要检查和设置一次，那么它可能理想地实现了这样的目的。但我的观点是，我遇到的几乎所有用例都不需要，并且当不需要时，涉及按位操作的旧学校方式往往效率更高。
是否有一个简短的测试分析std :: bitset vs 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;我得到以下结果：
Bool数组：随机访问时间= 4695，顺序访问时间= 390
位集：随机访问时间= 5382，顺序访问时间= 749
除了其他答案所说的访问性能之外，还可能存在显着的空间开销：典型的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位来存储单个位，使用位域方法，我只需要舍入到8位。
如果你有很多小的位集，这个因子八的空间使用会变得很重要。
这里不是一个很好的答案，而是一个相关的轶事：
几年前，我正在研究实时软件，我们遇到了调度问题。有一个模块超过了时间预算，这是非常令人惊讶的，因为模块只负责一些映射和打包/解压缩到32位字的位。
事实证明该模块使用的是std :: bitset。我们用手动操作替换它，执行时间从3毫秒减少到25微秒。这是一个重大的性能问题和显着的改进。
关键是，这个类引起的性能问题可能非常真实。
修辞问题：为什么std::bitset是用无效的方式写的？答：事实并非如此。
另一个修辞问题：有什么区别：
std::bitset<128> a = src;
a[i] = true;
a = a << 64;
和
std::bitset<129> a = src;
a[i] = true;
a = a << 63;
答案：性能http://quick-bench.com/iRokweQ6JqF2Il-T-9JSmR0bdyw的50倍差异
你需要非常小心你所要求的，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更便携，但也有成本：
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不需要比系统上可用的最大int更多的比特，因为其他明智的你需要拆分值来获得内部表中的正确元素。这意味着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