具有长位序列的二进制逻辑运算

Question

C++问题：

随机生成的 N Bit 序列（N 最多 50）

std::bitset<N> visit{0b01...110};

与从

std::bitset<N> ones{0b0}

、

std::bitset<N> ones{0b1}

开始并不断增长的 1 序列进行 XOR 运算的结果中应找到 1 的最小数量至

visit

的 MsB，所以

ones{0b111...111}

;

std::vector<int> countPenalty(std::bitset<N> set)
{
    std::bitset<N> closing{0b0};
    std::bitset<N> eins{0b1};
    std::vector<int> countPen; 
    countPen.reserve(N);

    while(std::bit_width(closing.to_ulong()) <= std::bit_width(set.to_ulong()))
    {  
        std::bitset<N> tempSet = set ^ closing; 
        countPen.push_back(std::popcount(tempSet.to_ulong()));
        closing <<= 1;
        closing |= eins;    
    }
     return countPen;
}


int main()
{
   std::string s{"-11--111"};
   std::bitset<N> visitorSet(s, 0, s.size(), '0', '1');
   std::vector<int> penalties = countPenalty(visitorSet);
   auto minRes = std::min_element(penalties.begin(), penalties.end());
   std::cout << *minRes << std::endl; //2
   return 0;
}

类似的任务经常可以在面试准备或c++编码作业或leetcode中找到（下面提到了我看到的一些类似的任务描述）。但我在 stackoverflow 上读到要使用 big std。用于二进制逻辑运算的位集并不是一个有效的解决方案。其实为什么不呢？但是有没有一种更优雅的方式不需要很多代码行呢？我的意思是没有人愿意在工作面试中编写超级复杂的代码。尤其是自 c++20 以来，bitset 不是一个很好的解决方案吗？

“代码的现实生活背景”：

有一个售票柜台，有人在那里工作。当还有顾客想要买票时，开放售票柜台才有意义。所以处罚有两种情况：

• 售票柜台开放但没有顾客
• 售票柜台已关闭，但仍有顾客。

他们每天都会列出一个列表，看第i小时内是否有客户（是 1，否 0）。对于 8 小时的一天来说，这将类似于以下

::string s{"01100111"};

。现在有一个问题，是否应该在特定时间关店以省钱。目标是尽可能减少处罚。

这里有参观者名单和开放时间（0=售票柜台开放，1=售票柜台关闭）

访问者位集和开始/结束位集之间的异或给出了惩罚集。在那里我可以找到最低处罚金额，其中会显示何时最好关闭售票柜台以省钱。

Answer 1

std::bitset

效率低下

但是我在 stackoverflow 上读到要使用 big std。用于二进制逻辑运算的位集并不是一个有效的解决方案。

这是真的。

std::bitset

的要求使其效率低下，例如

std::bitset::set

当索引超出范围时抛出异常。这会导致显着的代码生成差异：

#include <bitset>
#include <bit>
#include <cstdint>

auto set(std::bitset<64> x, std::size_t i) {
    x.set(i);
    return x;
}

auto set(std::uint64_t x, std::uint64_t i) {
    return x | (std::uint64_t{1} << i);
}

第一个函数编译为：

set(std::bitset<64ul>, unsigned long):
        mov     rdx, rsi
        cmp     rsi, 64
        jae     .error_handling_stuff
        bts     rdi, rdx
        mov     rax, rdi
        ret
.error_handling_stuff:
        [...]

第二个函数编译为：

set(unsigned long, unsigned long):
        mov     rax, rdi
        bts     rax, rsi
        ret

参见编译器资源管理器中的实时示例

查看更多讨论：std::bitset 的性能如何？

std::bitset

尽管效率低下，但可能是一个不错的选择

但是有没有一种更优雅的方式不需要很多代码行呢？我的意思是没有人愿意在工作面试中编写超级复杂的代码。尤其是自 c++20 以来，bitset 不是一个很好的解决方案吗？

我仍然会使用

std::bitset

，因为除了特定的性能关键用例之外，

std::bitset

足够好。 首先担心编写正确的代码，然后担心它是否高效（如果它还不够高效）。

另请参阅何时优化过早？

如果您接受

std::bitset

，您可以提高代码质量，这比了解与某些标准库类型相关的利基性能问题更能给您的雇主留下深刻的印象：

while(std::bit_width(closing.to_ulong()) <= std::bit_width(set.to_ulong()))
{  
    countPen.push_back((set ^ closing).count()); // use count() instead of std::popcount
    closing <<= 1;
    closing.set(0); // use set(0) instead of | here
}
return countPen;

如果您仍然担心性能，您可以创建自己的

std::bitset

风格的容器，它不执行运行时检查。