CF 1064B Equations of Mathematical Magic（思维规律）

Description

Colossal! — exclaimed Hawk-nose. — A programmer! That's exactly what we are looking for.

Arkadi and Boris Strugatsky. Monday starts on Saturday

Reading the book "Equations of Mathematical Magic" Roman Oira-Oira and Cristobal Junta found an interesting equation: a−(a⊕x)−x=0

for some given a, where ⊕ stands for a bitwise exclusive or (XOR) of two integers (this operation is denoted as ^ or xor in many modern programming languages). Oira-Oira quickly found some x

, which is the solution of the equation, but Cristobal Junta decided that Oira-Oira's result is not interesting enough, so he asked his colleague how many non-negative solutions of this equation exist. This task turned out to be too difficult for Oira-Oira, so he asks you to help.

Input

Each test contains several possible values of a

and your task is to find the number of equation's solution for each of them. The first line contains an integer t (1≤t≤1000

) — the number of these values.

The following t

lines contain the values of parameter a, each value is an integer from 0 to 230−1

inclusive.

Output

For each value of a

print exactly one integer — the number of non-negative solutions of the equation for the given value of the parameter. Print answers in the same order as values of a

appear in the input.

One can show that the number of solutions is always finite.

Sample Input

Input

Output

1
2
1073741824

题目意思：已知a,求解方程a−(a⊕x)−x=0，x的可能情况有几种。
解题思路：通过移项我们可以得到a⊕x=a-x，那么我们需要找一下这两个表达式的联系和区别。因为是异或，我们将这两个数放在二进制下比较。

1^1=0 1-1=0
   1^0=1 1-0=1
   0^0=0 0-0=0
   0^1=1 0-1=1//借位

我们可以发现,当a=1时，不管对于位上的x是0还是1，都是成立的，但当a=0时，只有x=0成立。
因而发现a=1时可以有两种选择，那么只需要统计a的二进制中1的个数，根据乘法原则就能求出所有解的个数了。

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<cmath>

using namespace std;

/*

1^1=0 1-1=0

1^0=1 1-0=1

0^0=0 0-0=0

0^1=1 0-1=1//借位

*/

int main()

{

   int a,b,t,ans;

   scanf("%d",&t);

   while(t--)

   {

     scanf("%d",&a);

     ans=;

     while(a)

     {

         if(a%)

         {

             ans=ans*;

         }

         a/=;

     }

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

   }

   return ;

}

巴特西

CF 1064B Equations of Mathematical Magic（思维规律）

最新文章

热门文章