시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 346 214 163 65.726%

문제

여러분은 Q개의 쿼리를 수행해야 합니다. 수행해야 하는 쿼리는 다음과 같습니다.

어떤 수 a를 2의 거듭제곱 꼴로 나타낼 수 있는가?

입력

첫 줄에 Q가 주어집니다. (1 ≤ Q ≤ 106)

두 번째 줄부터 Q+1번째 줄까지 a가 주어집니다. a는 1이상 231-1이하 자연수입니다.

출력

각 쿼리마다, 답이 Yes이면 1을, 그렇지 않으면 0을 출력합니다.

예제 입력 1

10
1
2
7
4
14
32
33
34
35
36

예제 출력 1

1
1
0
1
0
1
0
0
0
0

힌트

어떤 수 a가 2의 거듭제곱꼴로 나타내어진다고 해 봅시다. 그렇다면, a = 2n (단 n ≥ 0인 정수) 를 만족할 겁니다. 보통, 각 비트별로 검사를 하면서, 켜져 있는 비트의 개수를 알아내는 것도 좋은 방법입니다. 이 때에는, 많아봤자 32번 정도 연산을 수행하고, 전체 쿼리가 Q개 있다면, 총 시간 복잡도는 O(32Q)가 됩니다.

그런데, 더 좋은 방법이 없을까요? x (x ≥ 0)를 2진법으로 표현해 볼건데요. x가 홀수인 경우와 짝수인 경우로 나눠 봅시다.

...01

이 때 -x는 어떻게 표현이 될까요?

...11

따라서, x&(-x)를 하면 1이 나옵니다. x가 짝수라면 어떨까요?

...10…0

으로 표현이 될 겁니다. 이 때 -x는 어떻게 표현이 될까요? 일단 bit 반전 먼저 시켜봅시다.

...01...1

이 되고, 여기에 1을 더한 것이 2의 보수 표현법입니다. 따라서 -x는

...10...0

으로 표현됩니다. 따라서 x&(-x)는 1이 있는 x의 최하위 bit와 관련이 있음을 알 수 있습니다. 예제를 하나 들어봅시다. x=6인 경우 x&(-x)의 값은 어떻게 나올까요?

6 = ...0110

-6 = ...1010

이므로 6&(-6) = 2가 나옵니다.

그러면, a가 2i꼴로 나타내어진다면, 어떤 성질이 있는지를 관찰해 봅시다.

a = 0...010...0

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

따라서 (a&(-a)) == a라면 2의 거듭제곱이고, 그렇지 않으면 2의 거듭제곱이 아닙니다.