求二进制数中1的个数

开始找工作了，笔试面试中难免会碰到一些算法题，准备从今天开始，每天总结一些值得注意的题目。

现在主要从【编程之美】这本书中摘选吧。

 

题目：对于一个字节（8位）的无符号整型变量，求其二进制表示中“1”的个数，要求算法的执行效率尽可能高。

书中总共给出了五种解法，我觉得比较实用的就前三种，后两种（使用分支操作和查表法现实中很难用到）

最好的方法当然是第三种了，当位数多时，效果更明显。

public class BinaralySearch {
	
	public static void main(String[] args) {
		int i = 444444444; //十进制数
		String binary = Integer.toBinaryString(i);		
		System.out.println("Binary value of " + i + " is " + binary + ".");
		System.out.println(count1(i));	
		System.out.println(count2(i));	
		System.out.println(count3(i));		
		
	}

	//解法一，根据除法的特性，如果除以2余1，说明当前位为1
	public static int count1(int  a){
		int count=0;		
		while(a>0){
			if(a%2==1)count++;//除2余1
			a/=2;
		}
		return count;
	}
	//解法二，除2可以用右移一位来实现
	//同时，判断最后一位是否为1也可以用&操作来实现
	public static int count2(int  a){
		int count=0;
		while(a>0){			
			count+=a&0x01;//用&操作判断最后一位是否为1
			a>>=1;
		}
		return count;
	}
	
	//解法一，二的本质都是相同的，都是用除2来实现的，得循环8次
	//解法三的思路很巧，只需循环1的个数次即可
	//每次循环都把最低位的1去掉了
	public static int count3(int  a){
		int count=0;
		while(a>0){			
			count++;
			a&=(a-1);//通过&运算把最低位的1变成0
		}
		return count;
	}

}

 

扩展问题1：如果是32位时，应该用哪种方法，显然应该用第三种

扩展问题2：判断整数A和B的二进制表示中有多少位是不同的。

A,B先做异或，再求1的个数，

public static int differentBit(int a,int b){		
		return count3(a^b);
	}