题目描述:
给定一个数,输出这个整数的二进制中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