ac_801二进制中1的个数

题目描述

题目大意&链接

求出给定数列中每个数的二进制表示中 1 的个数。

输入输出样例：
输入：

5
1 2 3 4 5

输出：

1 1 2 1 2

详情：ac_801二进制中1的个数

解题思路

这题求二进制数就是采用“除基取余”法：

1. 将一个数除以2得到的余数作二进制数的数值位（低位），循环进行直到这个数除以2商是0，它的余数为最高位，这样的余数组成的数就是这个数的二进制数：

   int tmp = q[i], cnt = 0;
   while(tmp != 0)
   {
       if(tmp % 2 == 1) cnt++;
       tmp/=2;
   }
   printf("%d ", cnt);

完整代码

#include<iostream>

using namespace std;

const int N = 1e6 + 10;
int n;
int q[N];

int main()
{
    scanf("%d", &n);
    for(int i = 0; i < n; i++) scanf("%d", &q[i]);
    
    for(int i = 0; i < n; i++)
    {
        int tmp = q[i], cnt = 0;
        while(tmp != 0)
        {
            if(tmp % 2 == 1) cnt++;
            tmp/=2;
        }
        printf("%d ", cnt);
    }
    return 0;
}

时间和空间复杂度

时间复杂度：O(n)
空间复杂度：O(n)