如何求二进制数中1的个数

题目描述：

  给定一个数，输出这个整数的二进制中1的个数。
分析：

方法一：移位法

  可以使用位来操作来完成。首先，判断这个数的最后一位是否位1，如果为1，则计数器加1.然后，通过右移丢弃掉最后一位，循环执行该操作直到这个数等于0为止。在噢安段二进制表示的最后一位是否为1时，可以采用“与”运算来到达这个目的。

实现代码：

package lock;

public class T19 {
	/*判断n二进制码中1的个数*/
	public static int countOne(int n)
	{
		int count=0;   //用来计数
		while(n>0)
		{
			if((n&1)==1)  //判断最后一位是否为1
				count++;
			n>>=1;  //移丢掉最后一位
		}
		return count;
	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		System.out.println(countOne(7));
		System.out.println(countOne(8));
	}

}

运行结果：

算法性能分析：

  这种算法的时间复杂度为O(N)，其中N代表二进制的位数。

方法二：“与”操作法

  给定一个数n，每进行一次n&(n-1)计算，其中结果都会少了一位1，而且是最后一位。通过不断的用n&(n-1)操作去掉n中最后一位1的方法求出n中1的个数。

实现代码：

package lock;

public class T20 {
	public static int countOne(int n)
	{
		int count=0;   //用来计数
		while(n>0)
		{
			if(n!=0) //判断最后一位是否为1
				n=n&(n-1);
			count++;
		}
		return count; 
	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		System.out.println(countOne(7));
		System.out.println(countOne(8));
	}

}

运行结果：

算法性能分析：

  这种算法的时间复杂度为O(m)，其中m为二进制数中的个数。显然，当二进制数中1的个数比较少时，这种方法有更高的效率。

本文地址：https://blog.csdn.net/qq_45828598/article/details/109251844