剣指offer---バイナリ中1の個数C++題解

C++は、実はポイントでビット演算と言っているので、まずビット演算を利用することを考えるべきです.
ビットと(&)演算子
その名の通り、操作数のバイナリを演算します.例えば2&1で、結果は0です.バイナリ計算10&01は00ですから.
n&n-1は何をしましたか
例を挙げると,n=10,nのバイナリが1010,n−1すなわち9,バイナリが1001であると仮定すると,1010&1001を用いた結果,1000となり,元のn=1010に比べて右から最初の1がなくなったことが分かった.
分析してみると、n-1のバイナリ値は必ず元のバイナリ値の右から最初の1を0にし、この1の右のすべての0が1になり、さらにビットと演算を行うと、nバイナリの中で右から最初の1を取り除くと同時に、n-1バイナリが増えたばかりの1も0になるので、n&n-1に比べて右から最初の1が少なくなります.
次のように計算します.

while (n) {
    n = n & n - 1;
}

ループごとに右端の1が消去され、すべての1が消去されるまで消去されるので、変数をカウントするだけでnバイナリの1の個数を統計することができます.
コードは次のとおりです.

class Solution {
public:
     int  NumberOf1(int n) {
         int cnt = 0;
         while (n) {
             cnt++;
             n = n & (n-1);
         }
         return cnt;
     }
};