AcWing 801. 二进制中1的个数
原题链接
简单
作者:
小呆呆
,
2019-11-05 12:42:16
,
所有人可见
,
阅读 727
算法1
- 通过
lowbit(n) = n & -n
算法,返回n
中的最后一个1
,
- 若
n
中能找到存在符合lowbit(n)
的1
时,count++
,n-=lowbit(n)
时间复杂度 $O(1)$
Java 代码
import java.util.*;
public class Main{
//返回n的最后一个1
public static int lowbit(int n)
{
return n & -n;
}
public static int findOne(int n)
{
int count = 0;
while(n > 0)
{
n -= lowbit(n);
count ++;
}
return count;
}
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
int n = scan.nextInt();
for(int i = 0;i < n;i++)
System.out.print(findOne(scan.nextInt()) + " ");
}
}