CODEWITHSUNDEEP
c++algorithmbitset
gibraltar
gibraltar

Reputation: 1708

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.

Upvotes: 1

Views: 1133

Answers (2)

Mike Seymour
Mike Seymour

Reputation: 254651

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 example

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

In C++11, there is also a to_ullong() function, giving unsigned long long, which may be larger than unsigned 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.

Upvotes: 1

Piotr Kukielka
Piotr Kukielka

Reputation: 3872

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

Upvotes: 1

Related Questions