10.二进制中1的个数(JAVA)

二进制中1的个数

题目描述

输入一个整数，输出该数二进制表示中1的个数。其中负数用补码表示。

具体实现：

解法一：

解题思路：为了避免移位n的时候出现死循环的问题，创建一个flag=1来和n与操作，来判断n的最低位是否为1。

接着把flag左移移位得到2，再和n与操作，就能判断n的次低位是否为1，…这样循环左移，每次都能判断n的一位是否为1.

public class Solution {
    public  int NumberOf1(int n) {
    	int flag = 1;
    	int sum = 0;//1的个数
    	while(flag != 0) {	//flag左移到最后溢出会变成0则跳出循环
    		if( (flag & n) != 0) {	//flag(其中只有一位有1)和n做与操作，判断n中当前位是否是1.
    			sum++;
    		}
    		flag = flag << 1;//flag左移一位
    	}
    	return sum;
    }
}

解法二：

解题思路：把一个整数减去1，再喝原整数做与运算，会把该整数最右边一个1编程0.那么一个整数的二进制表示中有多少个1，就可以进行多少次这样的操作。

public int NumberOf1(int n) {
		 int sum = 0;
		 while( n != 0) {
			 ++sum;
			 n = n & (n-1);//n去掉了最右边的一个1
		 }
		 return sum;
	 }