消减整数

题目链接：nowcoder 219038

到主站看：https://blog.csdn.net/weixin_43346722/article/details/116171958

题目大意

给你一个数，然后你可以从减 1 开始，接着每次减的要么跟上一次一样，要么是它的两倍，问你最少把减多少次才能把它减到 0。

思路

这道题我们考虑用贪心来做。

那它每次减的可以跟原来一样，也可以翻倍。
那为了让我们减的次数最小，我们肯定是能翻倍就翻倍啊。

那怎么看能不能翻倍呢？
由于你翻倍之后至少都要减它，你要刚好减到 0，就是它剩下的数是它的倍数。

那就可以了，直接贪心就可以了。

代码

#include<cstdio>
#define ll long long

using namespace std;

int T;
ll h, ans, two;

int main() {
    scanf("%d", &T);
    while (T--) {
        ans = 0;
        two = 1;

        scanf("%lld", &h);
        while (h) {
            h -= two;//减
            ans++;//统计次数
            if (h % (2 * two) == 0) two *= 2;//能减两倍的就减两倍
        }

        printf("%d\n", ans);
    }

    return 0;
}