バイナリに変換せずにハミングウェイトを確認するにはどうすればよいですか?

StackOverflow https://stackoverflow.com/questions/843828

質問

どうすれば入手できますか 「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
役に立ちましたか？

解決

IMO、良いアプローチは、ルックアップテーブルを使用することです - （、それは一度だけ実行する必要がありますあなたはそれを生成するために、投稿のコードを使用することができます）1の数にバイトを変換辞書を作成し、そして、このようなものを使用します：

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

私は、これはかなり良いトレードオフスペースとランニングタイムの間にあると考えています。

他のヒント

私は、Pythonプログラマではないんだけど、うまくいけば、あなたが従うことのために十分なされます。

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

return c

少しあいまいなものの、それが主な利点は、スピードとシンプルさです。 whileループは、nは1にセットビット毎に一度だけ繰り返される。

あなたはこの計算が少ない複合体を作ることができません。 ;これはO（n）ビットの数、または、＆トリックとの答えが示されたように、O（n）が1に設定されたビットの数になります使用している数字のすべてが特別な場合でない限りしかし、後者は、平均してN / 2、そうものOの両方が（N）数が同じでなければならない。

とルックアップ・テーブルのトリックはもちろん、実際に計算の複雑さのために何もしていません。それだけでスペースと時間のために支払うが、根本的な経済学を変更せずに、一度、の何とかの各ビットを調べなければならないことであると、その周りに方法はありませんです。あなたは、論理的に、それらのそれぞれを検査することなく、数のビットについての質問に答えることはできません。

さて、私はこれらの例の多くは、実際にはO（n ^ 2）であるため、私は少しずさんされていたとPythonであなたが時間に一度、たとえば、のPythonの長整数とそうで全体の数を調べるために持っているので、 、100バイト、+またはAN及び/又は動作は、少なくとも一度は各バイトを見ていき、そして数は（上記に概説スキームに）ゼロに減少するまで、それが何度も起こるので、これらは、再び、あります実際にはO（n ^ 2）操作。私はPythonがここに真のO（n）のソリューションを許可することを確認していない。

とにかく：あなたは本当に、特に大きな-O分析を意味し、の計算の複雑さ、について尋ねられた場合、それはあなたの答えです。 ： - ）

あなたは、単一の行でそれをしたい場合は、あなたが使用することができます：

sum( [x&(1<<i)>0 for i in range(32)] )

実際に速度を重視する場合は、C でコーディングしてください (「 この質問 方法については)、次のようなものを使用して C 実装とインターフェイスします。 ctypes.

ここます：

DEF BITCOUNT（int_no）：

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

このは（アルゴは私が思い出すことができない名前を持つ）は、もともとCにimplementated ...これを行うには、古いと効率的な方法かもしれません。私は願ってのためにそれが正常に動作し、それは他の人のために行います。

P =ラムダN：N 1つの+ P（N・（N-1））

nが0よりも大きいが、それは1つの+ Pを算出するスイッチである場合、

これは、短絡および再帰を使用して（N・（N-1））Pは（N・（N-1））のように呼ばれ、場合nが0であり、それはものの数がバイナリに存在する回数を実行するためには、0の複雑さO（n）を返します。

例：P（9）= 1 + P（8）= 1 + 1つの+ P（0）= 1 + 1 + 0 = 2

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top