C++計算バイナリ数のうち1の個数

2進数のうちの1の個数を計算する比較的精巧なやり方を見て、メモをとります(実は前に聞かれたので調べてみました…)

int CountOnes(int n) {
	int count = 0;
	while(n) {
		++count;
		n = n & (n - 1);
	}
	return count;
}

見たばかりの頃は考えがよく分からなかったので、自分でペンを持って勝手に引っ張って、考えが分かったので、簡単にまとめました.この方法の主な考え方は、現在の数字の中で最も右側の1を見つけることです.
考え方は簡単にまとめます:n-1(nが0でない場合)はnの最も右側の最初の1とそのビットの右側のすべてのビットを逆にして、この時操作を行って、この位置を0にします.
実は上の言叶を见ればいいのですが、考え方は简単で、考えが全く理解できないので、下の言叶を见なければなりません.
大まかに2つの状況に分けることができて、もちろん事実上同じ状況と見なすことができます:第1種:nの最も右側は1です.nの右端が1であれば、n−1は右端の方のみが0となり、n&(n−1)はnの右端の1位の1を取り除くことに相当する.例えば、nが0111の場合、n−1は0110となり、両者が一致し、結果としてn−1となり、このときn−1の個数はnの中より1少なく、右端の位は0となり、2番目の場合に移行する.
2つ目:nの一番右側は0です.このときn−1を計算する場合,nの最も右側の最初の1まで上へビットを借りる必要がある.例えば、nが1000の場合、n−1は0111であり、nの最初の1の右側のすべてのビットが1になり、元の1のビットが0になったことがわかる.注意初期時nの最初の1の右側のすべてのビットは0であり、n-1を計算するとこれらのビットはすべて1になり、このとき再操作すると、これらのビットは0になります.したがって、効果は「nの右側の最初の1のビットが0に設定されている」ということです.
最後に、nに1のビットが存在しない場合、nの値は0に等しく、whileループは終了する.この方法は,右から左へ直接シフトする方法よりも優れており,すべてのビットを遍歴する必要はなく,運転時間はn中の1の個数に関連する判断も少なくない.