Search code examples
c++algorithmbitset

Implementing a binary counter using std::bitset

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.

Solution

  • 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