キー指offer——面接問題15:バイナリ中1の個数(p 99-103)

タイトルの説明
関数を実装して、整数を入力して、その数のバイナリ表現の中の1の数を出力してください.
例:9のバイナリ表現は1001で,2ビットが1である.
クラシック解法(タイムアウト)
分析:1つのflag = 1を譲って、それからnと付き合って、結果が1ならば最後の位置が1であることを証明します;次にflagを左に移動させ、nと乗算し、最終的にcount変数で原数nの1の個数に統計する.
古典的な解法コード:

//     1   
#include
using namespace std;

int main()
{
     
	//    
	int n = 10;
	int flag = 1;
	int count = 0;
	while(flag)//32  int      32 
	{
     
		if(n&flag)//        1，  flag     
		{
     
			count++;
		}
		flag = flag<<1;
	}
	cout<<count<<endl;

	return 0;
}

アップグレード解法(AC)
解析:実はn = n&(n-1);で、操作するたびにnの中の1は1つ少なくなって、nが0になって統計サイクルを終了するまで.まとめ1:整数から1を引くと、右端の1を0にします.右に0がある場合、すべての0は1になり、彼の左のすべてのビットは残ります.まとめ2:1つの整数から1を減算し、元の整数と演算すると、その整数の右端の1が0になります.整数のバイナリに1ビットが何個あるかを統計するには、このような操作を何回できるかを見ます.
コード:

//    
	int n =10;
	int count = 0;
	while(n)
	{
     
		count++;
		n = n&(n-1);
	}
	cout<<count<<endl;
	return 0;

広がる

は、1つの整数が2の整数次数であるか否かを1つの文で判断する.解析:1つの整数が2の整数次数である場合、そのバイナリ表現には1ビットのみが1であり、他の未ビットは0である.

コード:

if((n&(n-1)) == 0)
	return 1;

は、2つの整数mおよびnを入力し、mおよびnのバイナリビット数の異なる個数を計算する.解析:まずmとnを異ならせ,このようにして得られたmとnのビットの異なる位置が1であり,同じで0であり,次いで以上の統計法で1の個数を統計すればよい.

コード:

x = m^n;
while(x)
{
     
	count++:
	x = x&(x-1);	
}

左シフトと右シフト左シフト:右補0右シフト左補0.シンボルなしでn個の0を補い、シンボルがn個の1を補う.