剑指OFFER 面试题15（二进制）：二进制中1的个数 （JAVA）

题目

　　请实现一个函数，输入一个整数，输出该数二进制表示中1的个数。例如把9表示成二进制是1001，有2位是1。因此如果输入9，该函数输出2。

知识点（二进制的位运算）

二进制的位运算只有五种运算（与、或、异或、左移和右移）。

左移运算m<<n表示把m左移n位，在左移n位的时候，最左边n位将被丢弃，同时在最右边补上n个0，例如：

00001010<<2 = 00101000

10001010<<3 = 01010000

右移运算m>>n表示把m右移n位。在右移n位的时候，最右边的n位将被丢弃。但右移处理最左位的情况稍有些复杂。如果最左边数字是一个无符号数值，则用0填补最左边的n位，若最左边是一个有符号的数值，则用数字的符号填补最左边的n位。例如：

00001010>>2 = 00000010

10001010>>3 = 11110001

方法1：

与运算“有一个性质：通过与对应位上为1，其余位为0的数进行与运算，可以某一整数指定位上的值。这道题中，先把整数n与1做与运算，判断最低位是否为1；接着把1左移一位，与n做与运算，可以判断次低位是否为1……反复左移，即可对每一个位置都进行判断，从而可以获得1的个数。

方法2：

如果一个整数不为0，把这个整数减1，那么原来处在整数最右边的1就会变为0，原来在1后面的所有的0都会变成1。其余所有位将不会受到影响。再把原来的整数和减去1之后的结果做与运算，从原来整数最右边一个1那一位开始所有位都会变成0。因此，把一个整数减1，再和原来的整数做与运算，会把该整数最右边的1变成0。这种方法，整数中有几个1，就只需要循环判断几次。

代码

public class Numberof1inBinary {
	public static int numof1(int n) {//方法1
		int count=0;
		int flag=1;
		while(flag!=0) {
			if ((flag&n)!=0)
				count++;
			flag=flag<<1;
		}
		return count;	
	}
	public static int numof1_1(int n) {//方法2
		int count=0;
		while (n!=0) {
			count++;
			n=(n-1)& n;
		}
		return count;
	}
	public static void main(String[] args) {
		System.out.println(numof1(3));
		System.out.println(numof1_1(3));
	}

}