c++ - 使用 std::bitset 实现二进制计数器

Question

我想在 C++ 中使用std::bitset. 如果我明确地开发一个加法函数，bitset那么算法的复杂度将上升到 O(n^2)。有没有办法做到这一点O（n）？

还有对 Horowitz 和 Sahni 的子集和问题解决方案有什么好的描述吗？除了维基百科，我找不到任何描述他们算法的好资料。

Answer 1

对于您的第二个问题，“Horowitz 和 Sahni 的子集和问题解决方案有什么好的描述吗？”，我发现了几篇文章：

Horowitz 和 Sahni 的原始论文：
http ://www.cise.ufl.edu/~sahni/papers/computingPartitions.pdf

Stackoverflow 关于 Horowitz 和 Sahni 算法改进的讨论：
生成范围内的所有子集总和比 O((k+N) * 2^(N/2)) 更快？

源代码：
http ://www.diku.dk/hjemmesider/ansatte/pisinger/subsum.c

Answer 2

如果位集足够小以至于所有位都可以放入unsigned long，那么您可以使用它的转换函数对其执行整数运算，例如

bitset = std::bitset(bitset.to_ulong() + 1);

在 C++11 中，还有一个to_ullong()函数 given unsigned long long，它可能大于unsigned long.

如果您的位集太大，您最好实现自己的位集，基于您的计数器可以访问的整数数组或向量。您的算法仍将是 O(n ² )，但与一次处理单个位相比，您可以减少每次加法所需的操作数。