algorithm - 二进制序列的求和

Question

考虑一个二进制序列：

11000111

我必须找到这个系列的总和（实际上是并行的）

总和 =1+1+0+0+0+1+1+1= 5

这是对资源的浪费，为什么要花时间添加 0？

有没有什么聪明的方法来总结这个序列，这样我就可以避免不必要的添加？

Answer 1

在字节级别而不是位级别进行操作。使用一个小的 LUT 将一个字节转换为一个人口计数。这样，您只需进行一次查找和每 8 位添加一次。除非您的数据可能非常稀疏，否则这应该非常有效。

Answer 2

我不知道为什么人们在回答，甚至没有查看从第一条评论到问题的链接。您可以轻松地将其制作在O(size_of_bitset). 至少在涉及常数因子时。

您可以使用此方法（在JF Sebastian的链接中找到）：

inline int count_bits(int num){
int sum = 0;
for (; bitset; sum++) bitset &= bitset-1;
return sum;
}

int main (void){
  int array[N];
  int total_sum = 0;
  #pragma omp parallel for reduction(+:total_sum)
  for (size_t i = 0; i < N, i++){
     total_sum += count_bits(array[i]);
  }
}

array这将并行计算内存范围内的位数。内联对于避免不必要的复制很重要，编译器也应该更好地优化它。

如果你找到任何东西，你可以count_bits用任何更好的东西来计算整数中的位，以便更快。这个版本的复杂度为O(bits_set)（不是位集的大小！）。

与需要相当大的单个求和来补偿的单个求和相比，调用并行构造将引入相当多的开销。

并行性是通过 OpenMP 完成的。每个线程的部分总和在并行循环结束时求和并存储在total_sum. 请注意，由于减少子句total_sum，每个线程的循环内部都是私有的。reduction

您可以更改代码以使其对设置在任意内存区域中的位进行计数，但是当您在如此低的级别上执行操作时，保持内存对齐非常重要。

Answer 3

好吧，这取决于您如何存储位集。如果它是一个数组，那么你只能做一个普通的 for。如果您想并行执行此操作，只需将数组拆分为块并同时处理它们。

如果我们谈论的是位集（将位存储在本机（32/64 位）整数类型中），那么对位进行计数的最简单方法是这个：

int bitset;
int s = 0;
for (; bitset; s++)
    bitset &= bitset-1;

这会在每一步中删除 1 的最后一位，因此您有 O(s)。

当然，如果你需要超过 32/64 位，你可以将这两种方法结合起来

Answer 4

据我所知，尝试专门处理零是浪费的。正如@bdares 所说，添加真的很便宜。至少，您需要执行 N 条指令来总结一个 N 位序列，如果您无条件地求和任何位。如果您添加一个测试以查看该位是 0 还是 1，则这是需要为每个位执行的另一条指令。即使没有分支惩罚，您也要为每个位执行至少 1 条指令（条件测试），然后您还要为任何等于 1 的位执行原始指令（加法）。所以即使没有分支惩罚，这需要更多的时间来执行。

@bdares 提到编译器会优化分支，但前提是每个位的值在编译时是已知的，并且如果您在编译时知道位的值，您应该提前自己添加它们。

玩弄一些小玩意可能会做一些可爱的事情。例如，如果您一次取两个位，您将添加 0、1、2 或 3 的值，并且只需要做一半的加法。然后您可以对结果进行一些操作，将其转换为您想要的值，但我实际上并没有考虑过如何做到这一点。