O（log n）内のC++ bitset論理演算？

Question

この投稿によるとPerformance of doing bitwise operations on bitsetsパフォーマンスはO（n）です。どうすればO（log n）にするのですか？おかげさまで

Answer 1

答えはありません。

ビットセットがnであるとします。 xor演算子^を見てみましょう。 明らかに両方のオペランドの各ビットを調べなければならないので、2nルックアップとなります。 この結果、O(n)の複雑さが生じます。

たとえば、次のようなアセンブラ命令を使用できます。一度に32ビットで処理するので、操作の数は(n+31)/32ですが、これは複雑さがO(n)であることは変わりません。すべての複雑さは無限に向かってnのために計算され、一定の要因は無視されます。