算法题：授勋

问题描述

历经旷日持久的战争之后，百纳瑞王国（TheKingdomofBinary ）终于迎来了胜利的曙光。于是国王决定在胜利日这一天为在战争中奋战的将领们授勋。 已经需要为 N 位将领授勋，他们每人有一个功勋值 p[i] 。国王准备了不同种类的勋章，它们分别代表 1,2,4,8,16......（即 2 的幂次）的功勋值。国王将用与每位将领功勋值对等数值的勋章授予他们，并且每位将领只会被授予一枚同种勋章。 现在请你帮助国王算出，对于每一位将领，他需要准备多少枚勋章？

输入格式

第一行输入一个数 N ，表示将领人数； 之后 N 行，每行输入一个数，分别表示每位将领的功勋值。

输出格式

输出 N 行，每行一个数表示需要授予该将领的勋章数。

样例

输入

3
15
1
22

输出

4
1
3

数据范围

对于 100% 的数据，2≤N≤10^5^. 1≤p[i]≤10^9^

解决方案

思路

位运算 取负数后，补码与原机器码做与运算可以提取到最低为1的二进制位

代码

#include <iostream>

using namespace std;

int main() {


    int t;
    cin >> t;

    for (int i = 0; i < t; ++i) {

        int n;
        cin >> n;

        int ans = 0;
        while (n) {
            n -= n & -n;
            ans++;
        }

        cout << ans << endl;

    }

    return 0;
}