K＆R Cプログラミング言語演習2-9

Question

私はK & R Cプログラミング言語、 第2章、2.10で、運動2-9を理解していない：

エクササイズ2-9。 2の補数システムでは、x & =（x-1）はxの右端の1ビットを削除します。理由を説明。この観測を使用して、より高速なバージョンのビットカウントを作成します。

BITCOUNT関数である：それはビット1であり、最後のビットにポップ場合

/* bitcount: count 1 bits in x */ 

int bitcount(unsigned x) 
{ 
    int b; 
    for (b = 0; x != 0; x >>= 1) 
     if (x & 01) 
      b++; 
    return b; 
} 

機能が確認した後、右端のビットを削除します。

なぜx&(x-1)が右端の1ビットを削除するのか理解できませんか？ 例えば、xが1010であり、x-1がバイナリで1001であり、x&(x-1)が1011であるとすると、右端のビットはそこにあり、1となるでしょう。

また、練習問題には2の補数が記載されていますが、この質問とは何か関係がありますか？

ありがとうございました!!!

Answer 1

なぜx & (x-1)右の最上位ビットを削除するのですか？ただ、試してみて、次を参照してください。

righmost上位ビットが1の場合、xはa...b1とx-1のバイナリ表現がa...b0でいるので、ビット単位と共通のビットはandと1 & 0によって変更されませんので、a...b1を与えるだろうが0

です

Else xはa...b10...0のバイナリ表現を持ちます。 x-1はa...b01...1であり、上記と同じ理由により、x & (x-1)は再び右端のオーダービットをクリアする。a...b00...0である。

どのビットが0でどれが1であるかを調べる代わりに、x = x & (x-1)はxが0になるまで操作を反復するだけです。ステップ数は1ビットの数になります。統計的にはステップ数の半分を使用するので、単純な実装よりも効率的です。コードの

例：

int bitcount(unsigned int x) { 
    int nb = 0; 
    while (x != 0) { 
     x &= x-1; 
     nb++ 
    } 
    return nb; 
}