テスト整数(バイナリ)は1個の数を含む


引用:中国のあるウイルス対策ソフト会社の2010年3月の筆記試験問題
#include <iostream>
using namespace std;
int func(int n)
{
	int nCount = 0;
	while( n )
	{
		nCount++;
		n = n & (n-1);
	}
	return nCount;
} 
int main(int argc, char *argv[])
{
	cout << func( 9999 ) << endl;
	return 0;
}

出力結果はいくらですか?
答えは:8
最初はテーマを見ていたが、私はできなかった.自分はビット操作にあまり慣れていないので、これが1を含む個数を求めていることを知っていても、まだ納得していない.
どうしてn=n&(n-1)で1の個数を求めることができるのか.
後で分析して、少し分かりました.
説明は以下のとおりです.
例えばあるバイナリ数n=1 xxxについて...100
ではn-1=1 xxx...011
ではn&(n-1)=1 xx...000
これにより,n&(n−1)演算を行うたびにnの末尾1が消去され,これにより毎回1が消去され,最後にnが0となり,nにどれだけの1が含まれているかが分かる.
添付:
ある面接問題では、整数が2のn次であるかどうかを1つの式で判断するように要求されていますが、実質的には、その整数が1を含む個数が0であるかどうかを判断すればいいのです.式は次のように表されます.
!(n & (n-1) )
本当なら説明します.
#include <stdio.h>
int GetOneCountsByDiv( int x )/* */
{
	int n=0;
	while( x )
	{
		if( x%2 ) n++;
		x /=2 ;
	}
	return n;
}

int GetOneCountsByMoveR( int x )/* */
{
	int n=0;
	while( x )
	{
		if( x&1 ) n++;
		x = x>>1;
	}
	return n;
}

int GetOneCountsByAnd( int x )/*n (n-1) */ 
{
	int n=0;
	while( x )
	{
		x &= (x-1);
		n++;
	}
	return n;
}
int main(int argc, char *argv[])
{
	printf( "%d", GetOneCountsByAnd(9) );
	return 0;
}