-1

ACM の問題を解決するプログラムを作成しようとしていますが、非常に高速でなければなりません。この問題に対する数学的に高速なアプローチは、ビット単位の計算を使用することです。ただし、私は python を使用しており、これらの計算をビット レベルで実行するのに問題があります。問題は次のとおりです。

  1. ビット内の 1 と 0 の数をカウントします。たとえば、2 進数の 100010 には 2 つの 1 と 4 つの 0 があることをどのように計算しますか。私が想像できる唯一のアプローチは、それを文字列に変換してカウントすることです。しかし、この変換は、最初にビット レベルで作業することによって得られたすべての速度を相殺します。
  2. 「100101」などの2進数をPythonで実際の2進数として記述する文字列入力を表す方法は? 現在、ビットを整数に変換する関数があり、int に対してビット演算を実行します。
  3. ビットデータ型はありますか？つまり、入力を文字列や整数ではなくビットとして受け取ることができますか?

C++ で bitSet などのクラスを作成することも検討しましたが、これもそれほど高速ではないと感じています。PS私が扱っている2進数は1000ビットにもなる可能性があり、1000個のそのような2進数で作業する必要があるかもしれないので、効率が不可欠です。

4

1 に答える 1

1

1 ビットをカウントするためのよく知られたアルゴリズムを次に示します。

def bitCount(x):
    count = 0
    while x != 0:
       count += 1
       x &= (x-1)
    return count

ポイントは、最下位の 1 ビットが 0 にクリアされ、後続の 0 がすべて 1 に設定されることを除いて、x-1 は x と同じバイナリ表現を持つことです。したがって、設定x = x & (x-1)すると、最下位の 1 ビットが単純にクリアされます。

于 2015-11-19T00:25:42.953 に答える