1

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.

Null
  • 1,950
  • 9
  • 30
  • 33
gibraltar
  • 1,678
  • 4
  • 20
  • 33
  • 1
    It already is O(n) because of amortization. – flight Oct 03 '11 at 11:41
  • @quasiverse can you please elaborate on the above point? – gibraltar Oct 03 '11 at 11:42
  • @quasiverse: if I got what you're referring to, bitset natively has no amortization, since it's a fixed-length container. – Matteo Italia Oct 03 '11 at 12:06
  • it may be helpful to know why you want to do this with a bitset rather than an int – jk. Oct 03 '11 at 12:07
  • @jk. As you can infer easily , I am trying to solve the subset sum problem. In order to compute the sum of a subset quickly, I have implemented a function for taking dot product between a bitset and a vector . Also std::bitset provides me with wide array of useful functions which otherwise i would have to write by myself. But I am open to suggestions, If there are any other data structures that can be used in place instead of std::bitset – gibraltar Oct 03 '11 at 12:23

2 Answers2

1

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

Community
  • 1
  • 1
Piotr Kukielka
  • 3,792
  • 3
  • 32
  • 40
1

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.

Mike Seymour
  • 249,747
  • 28
  • 448
  • 644
  • +1 this was basically what I was thinking except maintaining a separate unsigned long to maintain the counter – jk. Oct 03 '11 at 13:15