6

重複の可能性：
n＆（n-1）この式は何をしますか？

次のアルゴリズムを検討してください。

int count(int num)
{
  int ones = 0;
  while(num)
  {
    ++ones; 
    num &= num - 1;
  }

  return ones;
}

の意味は何num & (num-1)ですか？それはどのように機能しますか？

4

3 に答える 3

7 
num &= num - 1;

numに設定されている最下位ビットをクリアします。

このアルゴリズムは、設定されたビットをクリアし、すべてなくなるまでカウンターをインクリメントすることによってカウントします。

最下位ビットをクリアする理由を理解するには、デクリメントがビットに対して何を行うかを考え、もちろん&操作が何を行うかを理解する必要があります。

バイナリで減算することは、私たち全員が子供として10進数で教えられたプロセスと同じように機能します。右（最下位）から左に向かって作業し、可能な場合は個々の桁を減算し、必要に応じて次の桁から「借用」します。

ゼロのセットで終わる2進数から1を引く場合、この「借用」と減算により、右端の1から1よりも低い位置にあるすべてのゼロが変わり、右端の1がゼロになります（借用されたため）。

次に、&演算子を適用すると、下位桁はすべてゼロであるためゼロのままにnumなり、最下位ビットはnumゼロであるためゼロに設定されnum-1ます。

これらの操作はどちらも、有効数字を変更せずに残します。

これは、ブライアン・カーニハンによるものである、これを含むビットをいじるハックの良いリストです。

于 2012-08-04T17:25:57.140 に答える
7

これがより詳細な（しかしあまりよく書かれていない！）答えです。

2つのケースがあります：最下位ビットが設定され、次に「num-1」がそれを設定解除します。または、設定されていない場合、num-1はすべての後続ゼロを1に変換し、最下位の1を0に変換し、残りのビットは変更されません。「and」を指定すると、変更されていないすべてのビットが同じになり、0が付いている最下位の1が0になり、残りのビットはゼロになります。これはここに示されています：

num             =      1000110111[1]0000
num - 1         =      1000110111[0]1111
num & (num - 1) =      1000110111[0]0000

1サイクルで1の数を数えるための組み立て作業がよくあることを指摘しておきます。この操作は「popcount」と呼ばれ、たとえばGCCでは、「__builtin_popcount」を使用してアクセスできます。詳細については、このリンクを参照してください。

于 2012-08-04T17:35:45.763 に答える
-1

アルゴリズムはポンプのように動作し、ビットを「num」変数内で効果的に右に移動します。この線

num &= num - 1;

作業が行われる場所であり、割り当てとブールAND演算が同時に実行されます。それはすべてビット演算に関するものです。

ポン

于 2012-08-04T17:42:55.877 に答える