c++ - 向量的按位运算

Question

执行按位运算的最佳方法是vector<bool>什么？

据我了解，vector<bool>是一种每个布尔值使用一位的专业化。我选择vector<bool>了节省内存的原因。我知道有一些问题，vector<bool>但对于我的需要，它是适当的。

现在 - 将按位运算应用于整个此类向量的最高效方法是什么？

如果我在 for 循环中执行它并读出每个布尔值并将其存储回来，我理解它的方式是在内部执行更多操作以访问实际值。

谢谢！

Answer 1

如果位数在编译时是固定的，那么最好使用std::bitset

如果不是，（即位数在运行时变化），那么您应该看到并可以使用boost::dynamic_bitset）

在这两种情况下，执行所有按位运算都非常容易。

Answer 2

忽略问题的标题，让我们回答这个问题，而不是：

对向量执行按位运算的最佳方法是什么？

最好的方法是将向量定义为vector<unsigned char>（或vector<uint32_t>，或您选择的任何其他整数类型），并按照通常对无符号整数数组的方式进行按位运算。这样事情会快很多，而且不会有隐藏的机制。

您可以使用除法（或按位运算符，如果您很聪明的话）来解决您需要对哪个数组索引进行操作，并使用 for 循环来应用大于单个元素的按位运算。

这是一个相关的问题： Bit twiddling a lot of bits in C

如果您决定使用自己的运算符进行包装vector<unsigned some-int-type>，您基本上将执行这些相同的操作。

Answer 3

我阅读了这两个答案，但只是想要一个快速的解决方案，并实施了一些可怕的事情。

您可以使按位运算符工作vector<bool>，但代码必须专门用于 c++ 标准库实现或回退到慢速形式。这是我operator|的 GNU libstdc++-v3：

std::vector<bool> operator|(std::vector<bool> A, const std::vector<bool>& B)
{
    if (A.size() != B.size())
        throw std::invalid_argument("differently sized bitwise operands");

    std::vector<bool>::iterator itA = A.begin();
    std::vector<bool>::const_iterator itB = B.begin();

    // c++ implementation-specific
    while (itA < A.end())
        *(itA._M_p ++) |= *(itB._M_p ++); // word-at-a-time bitwise operation

    return A;
}

这当然很糟糕。有人更新 GCC，新版本以不同的方式存储内容，并且您的代码无缘无故地中断。

Answer 4

这个也应该工作。

std::vector<bool> v3(v1.size());
std::transform(v1.begin(), v1.end(), 
               v2.begin(), v3.begin(), std::logical_and<bool>());