题目描述

给定一个长度为n的数列，请你求出数列中每个数的二进制表示中1的个数。

样例

15

1111

算法

(整数n的右移)

1. 求整数n的第k位数字是0还是1。
2. 将n的第k位数字移动到个位——$n >> k$，本质上是将整数n的第k位数字移动到个位。
3. 最后与1进行&操作——$n >> k & 1$
4. 可以再拿整数10来举个栗子，清晰一些。10的二进制表示是1010，右移0位是1010(不动)；右移1位是101，右移2位是10，右移3位是1。也就是说，对于数字10，右移3位就是把最高位移动到了个位。

C++ 代码

#include <iostream>

using namespace std;

int main()
{
    int n = 15;
    for(int k = 3; k >= 0; k --) cout << (n >> k & 1);

    return 0;
}

算法

(lowbit())

1. 树状数组的基本操作
2. 作用：返回x的最后一位1——假如x = 1010，那么lowbit(x) = 10；x = 101000，那么lowbit(x) = 1000。
3. lowbit()的代码实现是$x & -x$，或者是$x & (~x + 1)$，补码是-x，反码是~x。
4. 可以用lowbit()函数来统计整数x中，1的个数，每次都把x中的最后一位1去掉，减了多少次，就有多少个1。所以算法实现就是——每次减去x的最后一位1，对应的res ++。

时间复杂度

$O(1)$

C++ 代码

#include <iostream>

using namespace std;

const int N = 100010;

int lowbit(int x)
{
    return x & -x;
}

int main()
{
    int n;
    cin >> n;
    while(n --)
    {
        int x;
        cin >> x;

        int res = 0;
        while(x) x -= lowbit(x), res ++;

        cout << res << ' ';
    }
}

补充

再补充一些原码，补码，反码的知识。计算机中的负数是用补码来表示的，而不是反码。因为计算机底层是做不了减法的，只能用加法来做减法。所以-x就是0 - x，也就是100...00 - x，这个操作就是~x + 1，也就是补码。

-10

11111111111111111111111111110110

C++ 代码

#include <iostream>

using namespace std;

int main()
{
    int n = 10;
    unsigned int x = -n;

    for(int i = 31; i >= 0; i --) cout << (x >> i & 1);
    cout << endl;

    return 0;
}