Yet Another No-Solve Prevention Problem!!

You must process $Q$ queries. Each query is the following.

Can the number $a$ be written as a power of two?

The first line gives $Q$. ($1 \le Q \le 10^6$)

The second line through the $(Q+1)$-th line give $a$. Each $a$ is a natural number with $1 \le a \le 2^{31}-1$.

For each query, print 1 if the answer is Yes, and 0 otherwise.

Suppose some number $a$ can be written as a power of two. Then $a = 2^n$ for some integer $n \ge 0$. Usually, checking each bit and counting the number of set bits is also a good approach. This performs at most about 32 operations, so with $Q$ queries in total the time complexity is $O(32Q)$.

But is there a better way? Write $x$ ($x \ge 0$) in binary, and split into the cases where $x$ is odd and where $x$ is even.

...01

How is $-x$ written then?

...11

So $x\&(-x)$ gives 1. What if $x$ is even?

...10...0

This is how it is written. How is $-x$ written then? First flip the bits.

...01...1

Adding 1 to this is the two's complement representation. So $-x$ is written as

...10...0

Therefore $x\&(-x)$ is related to the lowest set bit of $x$. Here is an example. When $x=6$, what is the value of $x\&(-x)$?

$6 = ...0110$

$-6 = ...1010$

so $6\&(-6) = 2$.

Now observe what property $a$ has when it is written as $2^i$.

$a = 0...010...0$

$-a = 1...110...0$

So if $(a\&(-a)) == a$, then $a$ is a power of two; otherwise it is not.