c++ - std::bitsetを使用したバイナリカウンターの実装

Question

を使用してC++でバイナリカウンターを実装したいと思いstd::bitsetます。の加算関数を明示的に開発するbitsetと、アルゴリズムの複雑さはO（n ^ 2）になります。このO（n）を行う方法はありますか？

また、ホロウィッツとサーニの部分和問題の解決策についての良い説明はありますか？ウィキペディアを除いて、私は彼らのアルゴリズムを説明する良い情報源を見つけることができませんでした。

Answer 1

2番目の質問「ホロウィッツとサーニの部分和問題の解法についての良い説明はありますか？」について、私はいくつかの記事を見つけました。

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.c

Answer 2

ビットセットが十分に小さいためにすべてのビットが収まるunsigned long場合は、その変換関数を使用して、たとえば整数演算を実行できます。

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

C ++ 11にはto_ullong()、を与える関数もあります。unsigned long longこれは、より大きくなる可能性がありますunsigned long。

ビットセットが大きすぎる場合は、カウンターがアクセスできる整数の配列またはベクトルに基づいて、独自のビットセットを実装することをお勧めします。アルゴリズムは引き続きO（n ²）ですが、一度に1ビットを処理する場合と比較して、加算ごとに必要な演算の数を減らすことができます。