剣指offer面接問題15:バイナリ中1の個数(Java実現)

タイトル:整数を入力し、その数をバイナリで表す1の数を出力します.ここで負数は補数で表される.例えば入力9,9のバイナリ表現は1001,1の個数は2であるので出力2である.
試験例:1.正数(境界値1、0 x 7を含むFFFFFFF)2.負数(境界値0 x 8000000、0 xFFFFFFFFを含む)3.
方法1:従来の解法では、サイクル回数が整数バイナリのビット数に等しい
まずnと1を演算し,最低位が1であるか否かを判断し,次に1を左にシフトして10を得,nと演算し,nの次低位が1であるか否かを判断することで,左シフトを繰り返すことで,nの各位が1であるか否かを判断することができる.

public class test_fifteen {
	
	//   ，  
	public int numberOf1(int n){
		int count = 0;
		int flag = 1;
		while(flag!=0){
			if((n & flag)!=0)
				count++;
			flag = flag << 1;
		}
		return count;
	}
}

方法2:最適解,整数バイナリに1が何個あるかで何回操作する.
1つの整数が0でない場合、この整数の少なくとも1つは1である.この整数を1に減らすと、元の整数の右端にある1が0になり、元の1の後ろにあるすべての0が1になります(右端の1の後ろに0があれば).残りのすべてのビットは影響を受けません.たとえば、右から3番目のビットが最も右にある1つのバイナリ数1100です.1を減算と、3番目が0となり、その後ろの2番目の0が1となり、前の1は変わらないので、結果は1011となる.私たちは1を減らした結果、一番右の1から始まるすべてのビットを逆にしたことを発見しました.このとき、元の整数と1を減算した結果を演算すると、元の整数の一番右の1つからすべてのビットが0になります.1100&1011=1000のように重要な法則が得られます:1つの整数を1を減らして、元の整数と演算して、この整数の最も右の1を0にします.では、1つの整数のバイナリに1がいくつあるかで、このような操作を何回行うことができます. 

//   ，   
	public int numberOf1(int n){
		int count = 0;
		while(n!=0){
			count++;    //        0       1  
			n = n & (n-1);
		}
		return count;
	}