c++ - 使用位集在不使用循环的情况下获取数组项的条件和

Question

有一个位集b 和一个数组arr。我想通过使用 bitset 来获取数组的总和，以便 arr[i] 只有在设置了 b[i] 时才会求和。

示例:

bitset<4> b("1001"); 
arr[4] = {5,4,3,1};

===> the sum would be 1+5 = 6. 

显然，我可以使用循环。但是这种计算会重复多次。没有循环有没有更有效的方法？

Answer 1

最快的方法可能是遍历循环并根据当前位是否已设置进行添加。

也许使用位移位而不是直接访问位 n 可以避免标准库的一些隐藏体操来提取特定位，但这尚未通过基准测试证明。:

int sum=0;
for (size_t i=b.size(); i; i--, b>>=1) 
    if (b[0])
        sum+=arr[i-1];

为了完整性和乐趣，如果你能忍受 vector<bool>而不是 bitset<> ，你可以只使用标准库:

vector<bool> b{1,0,0,1}; 
int arr[4] = {5,4,3,1};
int test=inner_product(begin(arr), end(arr), b.begin(), 0); 

Online demo

---

编辑:附加信息——相信你的优化编译器

我在 x86-64 平台上使用 gcc 7.2 在 godbolt 在线编译器上进行了实验，以查看由上述不同变体生成的程序集。

最简单的解决方案，遍历循环并有条件地添加项目非常快:

• 使用您示例中的常量值，编译器能够通过常量传播并确定 6 的结果立即(参见 here)。
• 如果您的数据结构较小，编译器会自动展开循环，使循环变得非常快(14 sequential assembler instruction for 4 elements)，无需维护任何循环索引。
• 然而，优化器可能会选择不展开更大尺寸的循环。在我的实验中，循环展开的大小最多为 17 个项目，其中 18 个元素是 real loop。 )

位移位替代方案非常接近:

• 最多 17 个项目，展开循环，生成的代码与简单循环完全相同。
• 从18个元素开始，生成一个循环，其中有one assembly instruction less每次迭代。这似乎有点快，但只有基准才能真正产生可能在纳秒范围内的差异。

当然，inner_product更重，因为它确实进行了乘法运算，需要将 bool 转换为 int，并且它必须处理 bool vector 的动态大小。