A 数字游戏

题目大意：

给出一个数x，问需要几次操作使其变为零

思路：

首先预处理出二进制下有多少个一

分类讨论

注释：下面所以表示消掉1都是指除了最低位外的。

• 如果x是偶数（表示二进制下最低位为0）

  • 如果总共有奇数个一， 那么显然我们消掉除所有的一，每次都是需要最后一位取反，也就是两次操作，但是对于最后一次操作会使最低位变成1，次数为：cnt * 2 + 1;
  • 如果总共有偶数个一， 那么显然我们消掉除所有的一，每次都是需要最后一位取反，也就是两次操作，最后一次操作会使最低位变成0，次数为：cnt * 2;

• 如果x是奇数（表示二进制下最低位为1）

起始最低位就是为1

• 如果总共有奇数个一， 显然我们消掉除所有的一，每次都是需要最后一位取反，也就是两次操作，最后一次操作会使最低位变成0，由于最后一位也有一个1，次数为：（cnt - 1） * 2;
• 如果总共有偶数个一， 类比x为偶数时的情况二，次数为：（cnt - 1） * 2 + 1;

#include <cstdio>
#include <cstring>
#include <iostream>
#define ll long long

using namespace std;

inline ll read()
{
	char c;
	c = getchar();
	ll x = 0, f = 1;
	while(c < '0' || c > '9') 
	{
		if(c == '-') f = -1;
		c = getchar();
	}
	while(c >= '0' && c <= '9') x = x * 10 + (c - '0'), c = getchar();
	return x * f;
}

int T;
ll n, cnt, flag;

int main()
{
	scanf("%d", &T);
	while(T--)
	{
		n = read();
		if(n == 0) {printf("0\n"); continue;}
  		if(n == 1) {printf("1\n"); continue;}
		flag = n % 2;
		
		cnt = 0;
		while(n) cnt += (n % 2), n /= 2;
		if(!flag)
        {
            if(cnt % 2 == 0) printf("%lld\n", cnt * 2);
            else printf("%lld\n", cnt * 2 + 1);
        }
		else 
        {
            if(cnt % 2 == 0) printf("%lld\n", (cnt - 1) * 2);
            else printf("%lld\n", (cnt - 1) * 2 + 1);
        }
	}
	return 0;
}