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

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要重得多，因为它确实进行了乘法运算，需要将bools转换为ints，而且它必须应对bool向量的动态大小。

Answer 2

Is there a more effective way without a loop ?

常见的for循环总是存在三个很容易被回避的低效之处：步幅增量、循环结束测试和循环结束跳转。然而，这些都是非常小的，所以不要抱太大希望。

您可以轻松地 "unroll" 循环以获得非常小的收益，但要付出更多代码行的代价（以 space 换取性能）。随着 bitset 的大小和数组的增长，这个方案变得乏味......

std::bitset<4> b     (std::string("1001"));
std::array<int, 4> a {{5,4,3,1}};

// loop form
int sum = 0;               
for (uint i=0; i < 4; ++i) // stride increment, test end-of-loop
{
   if (b[i]) sum += a[i];
}                          // end-of-loop jump
std::cout << "\n  sum: " << sum << std::endl;


// unrolled loop form -- no stride increment, 
//                       no end-of-loop test, and
//                       no end-of-loop jump
sum = 0;
if (b[0]) sum += a[0];    
if (b[1]) sum += a[1];
if (b[2]) sum += a[2];
if (b[3]) sum += a[3];
// bigger array, more lines ...

std::cout << "\n  sum: " << sum << std::endl;

注意 - 类似的方法支持大循环。在此示例中，每个 'line' 执行 1 个总和。对于大循环，每一行都可以调用一个函数来执行这些行中的 10（或 100 或 1000，等等）。我不记得上次看到另一个程序员展开循环代码是什么时候了。增益很小。

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

Using a bitset to get a conditional sum of array items without using loop

c++

arrays

algorithm

sum

bitset

编辑：附加信息 - 相信您的优化编译器