使用 std::bitset 实现二进制计数器
我想使用 在 C++ 中实现 二进制计数器 std::bitset。如果我明确地为 bitset 开发一个加法函数，那么算法的复杂度将上升到 O(n^2)。有什么办法可以做到这个 O(n) 吗？
还有 Horowitz 和 Sahni 的子集和问题解决方案有什么好的描述吗？除了维基百科，我找不到任何描述他们算法的好资料。
I want to implement a binary counter in C++ using std::bitset. If I explicitly develop an addition function for bitset then the complexity of the algorithm would go up to O(n^2). Is there any way to do this O(n)?
Also are there any good descriptions of Horowitz and Sahni's Subset Sum Problem Solution? Except for Wikipedia, I couldn't find any good source describing their algorithm.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
对于你的第二个问题，“Horowitz 和 Sahni 的子集和问题解决方案有什么好的描述吗？”，我找到了几篇文章：
Horowitz 和 Sahni 的原始论文：
http://www.cise.ufl.edu/~sahni/papers/ computingPartitions.pdf
关于 Horowitz 和 Sahni 算法改进的 Stackoverflow 讨论：
更快地生成某个范围内的所有子集总和比 O((k+N) * 2^(N/2))？
源代码：
http://www.diku.dk/hjemmesider/ansatte/pisinger/subsum。
For your second question, "are there any good descriptions of Horowitz and Sahni's Subset Sum Problem Solution?", I found few articles:
Original paper from Horowitz and Sahni:
http://www.cise.ufl.edu/~sahni/papers/computingPartitions.pdf
Stackoverflow discussion about Horowitz and Sahni's algorithm improvements:
Generate all subset sums within a range faster than O((k+N) * 2^(N/2))?
Source code:
http://www.diku.dk/hjemmesider/ansatte/pisinger/subsum.c
如果位集足够小，所有位都可以放入
unsigned long，那么你可以使用它的转换函数对其进行整数运算，例如在C++11中，还有一个< code>to_ullong() 函数，给出
unsigned long long，它可能大于unsigned long。如果您的位集太大，那么您最好基于计数器可以访问的整数数组或整数向量来实现自己的位集。您的算法仍然是 O(n2)，但与一次处理一位相比，您可以减少每次加法所需的操作数。
If the bitset is small enough that all the bits can fit in
unsigned long, then you can use its conversion functions to perform integer arithmetic on it, for exampleIn C++11, there is also a
to_ullong()function, givingunsigned long long, which may be larger thanunsigned long.If your bitsets are too large for that, you may be better off implementing your own, based around an array or vector of integers that your counter can access. Your algorithm will still be O(n2), but you can reduce the number of operations needed for each addition, compared to processing a single bit at a time.