10

この特定の行がどのように機能するかについて説明が必要です。
この関数が 1 のビット数をカウントすることは知っていますが、この行はどのようにして右端の 1 ビットをクリアするのでしょうか?

int f(int n) {
    int c;
    for (c = 0; n != 0; ++c) 
        n = n & (n - 1);
    return c;
}

簡単に説明したり、「証拠」を提供したりできますか？

4

2 に答える 2

18

符号なし整数'n'は、最後のk桁が次のようになります。1の後に（k-1）個のゼロが続く：100 ... 0 kは1の場合もあり、ゼロはありません。

（n-1）は次の形式で終了します：ゼロの後に（k-1）1が続く：011 ... 1

したがって、n＆（n-1）は「k」ゼロで終了します：100 ... 0＆011 ... 1 = 000 ... 0

したがって、n＆（n-1）は右端の「1」を削除します。これを繰り返すたびに、基本的に右端の「1」桁が削除されるため、1の数を数えることができます。

于 2013-03-12T19:28:37.343 に答える
4

私はビット操作をブラッシュアップしており、これに出くわしました。今（3年後）の元のポスターには役に立たないかもしれませんが、他の視聴者のために品質を向上させるためにとにかく答えるつもりです.

n & (n-1)ゼロに等しいとはどういう意味ですか?

それがループを破る唯一の方法であるため、それを知っていることを確認する必要があります（n != 0）。としましょうn=8。そのビット表現は00001000. n-1(または 7)のビット表現は00000111. 演算子は、両方の&引数に設定されたビットを返します。00001000と に00000111は同様のビットが設定されていないため、結果は (またはゼロ) になります00000000。数字の 8 がランダムに選ばれたわけではないことに気付いたかもしれません。これはn2 の累乗の例でした。2 のすべての累乗 (2、4、8、16 など) は同じ結果になります。

指数が 2 でないものを渡すとどうなりますか? たとえば、 の場合n=6、ビット表現は00000110およびn-1=5または00000101です。&がこれら 2 つの引数に適用され、4 である 1 つの単一ビットのみが共通しています。n=4これはゼロではないため、インクリメントcして で同じプロセスを試しますn=4。上で見たように、4 は 2 の指数であるため、次の比較でループが中断されます。が 2 の累乗になるまで右端のビットを切り捨てます。n

とはc?

ループごとに 1 だけ増加し、0 から始まりますc。 は、数値が 2 の累乗に等しくなる前に切り取られるビット数です。

于 2016-04-01T13:30:41.513 に答える