14

実際に変換してカウントせずに、数値のバイナリ表現で「1」の数を取得するにはどうすればよいですか?

例えば

  def number_of_ones(n):
      # do something
      # I want to MAKE this FASTER (computationally less complex).
      c = 0
      while n:
        c += n%2
        n /= 2
      return c


>>> number_of_ones(5)
    2
>>> number_of_ones(4)
    1
4

8 に答える 8

12

私は python プログラマーではありませんが、うまくいけばそれで十分です。

c = 0
while n:
    c += 1
    n &= n - 1

return c

少しあいまいですが、主な利点は速度とシンプルさです。while ループは、n で 1 に設定されたすべてのビットに対して 1 回だけ繰り返されます。

于 2009-05-09T19:05:58.297 に答える
7

これを計算の複雑さを軽減することはできません。これは、O（n）ビット数、または＆トリックの答えが示すように、O（n）1に設定されたビット数になります。ただし、使用しているすべての数値が特殊なケースでない限り、後者は平均してn / 2である必要があるため、これらのO（n）数値は両方とも同じです。

もちろん、ルックアップテーブルのトリックは、計算の複雑さに対して実際には何もしていません。それは単にスペースで時間を費やしているだけですが、基礎となる経済学を変えることはありません。つまり、何らかの方法で各ビットを一度調べる必要があり、それを回避する方法はありません。論理的には、各ビットを調べずに、数値のビットに関する質問に答えることはできません。

Pythonでは一度に整数を調べる必要があるため、これらの例の多くは実際にはO（n ^ 2）であるため、少しずさんだと思います。たとえば、Pythonの長整数は100バイトです。 、+または＆または/操作は、各バイトを少なくとも1回調べます。これは、数がゼロに減少するまで何度も繰り返されるため（上​​記のスキームで）、これらも実際にはO（ n ^ 2）操作。Pythonがここで真のO（n）ソリューションを許可するかどうかはわかりません。

とにかく：計算の複雑さ、具体的にはビッグO分析を意味するものについて本当に質問しているのであれば、それがあなたの答えです。:-)

于 2009-05-09T20:12:20.213 に答える
5

IMO、良いアプローチは、ルックアップテーブルを使用することです-バイトを1の数に変換する辞書を作成します（投稿したコードを使用して生成できます。一度実行するだけで済みます）、次に何かを使用しますこのような：

def number_of_ones(n):
    sum = 0
    while n != 0:
        sum += lookup_table[n & 0xff]
        n >>= 8
    return sum

これは、スペースと実行時間の間のかなり良いトレードオフだと思います。

于 2009-05-09T19:46:52.630 に答える
4

1行で実行したい場合は、次を使用できます。

sum( [x&(1<<i)>0 for i in range(32)] )
于 2009-05-09T20:03:13.340 に答える
1

ここ：

def bitCount(int_no):

    c = 0
    while(int_no):
        int_no &= (int_no - 1)
        c += 1
    return c

これは、これを行うための古くて効率的な方法かもしれません...もともとCで実装されていました（Algoの名前は覚えていません）。それは私にとってはうまくいきます

于 2016-04-11T17:47:35.523 に答える
1

実際に速度が気になる場合は、C でコーディングし (方法についてはこの質問を参照してください)、 ctypesなどを使用して C 実装とやり取りします。

于 2009-05-09T19:12:23.477 に答える
0

p= ラムダ n:n および 1+p(n&(n-1))

これは、短絡と再帰を使用します。n が 0 より大きい場合、1+p(n&(n-1)) を計算するように切り替わり、p(n&(n-1)) が呼び出されます。n が 0 の場合は、以下同様です。 0 を返します。バイナリに存在する 1 の数だけ実行するため、複雑さは O(n) です。

例: p(9)=1+p(8)=1+1+p(0)=1+1+0=2

于 2016-04-08T15:03:25.387 に答える