バイナリの中の1の個数を解く

一:一般法

int BitCount(unsigned int n)
{
    unsigned int c =0 ; //    
    while (n >0)
    {
        if((n &1) ==1) //     1
            ++c ; //     1
        n >>=1 ; //   
    }
    return c ;
}

この方法は普通で、この数字のバイナリを直接求めてその中の1の数を見ることです.簡単ですが、時間の複雑さはnの増加とともに増加します.
二:快速法

<pre name="code" class="cpp">int BitCount(unsigned int n)

｛ int num = 0 ; while(n){ num++; n = (n-1)&n; } return num ; }
この方法はnが大きい時にずっと速くなって、nの中の1の個数が何個あるため、この高速法の時間の複雑度はいくらです.
どのように理解しますか.n=n&(n−1)は,nのうち最も右側の1つを毎回削除する.もしnがバイナリの中で最低位が1であれば、n-1は直接最後のビットを0に変えて、その他は変わらないで、このようにn&(n-1)演算を行う時最後のビットを除いてその他はすべて同じなので、直接最も右の1を取り除いて、;もしnがバイナリの中で最低位が0であれば、n-1は前に借りて、右端が1の位になるまで借りて、このようにn-1とn右端の1の左側はすべて同じで、右側はすべて反対で、n&(n-1)操作を行った後にこの1の位置が0,1右端のある数字もすべて0になって、このように右端の1を取り除きました.
例を挙げると、1つのバイナリ数1100で、右から3番目のビットは最も右にある1です.1を減算と、3番目が0となり、その後ろの2番目の0が1となり、前の1は変わらないので、結果は1011となる.私たちは1を減らした結果、一番右の1から始まるすべてのビットを逆にしたことを発見しました.このとき、元の整数と1を減算した結果を演算すると、元の整数の一番右の1つからすべてのビットが0になります.例えば1100&1011=1000である.すなわち、1つの整数から1を減算元の整数と演算すると、その整数の右端の1つが0になる.では、1つの整数のバイナリに1がいくつあるかで、このような操作を何回行うことができます.