알고리즘_부산코딩대회준비_수의 비밀

유적지에 2^k(0<= k) 의 형태가 의미있는 숫자라서, 숫자를 입력으로 주면 의미있는 숫자인지 찾는 것이다. 

 

나는 for문으로도 풀고 재귀로도 풀었는데 계속 한 사례가 잘 풀어지지 않았다. 

 

#include <stdio.h>



int main() {
	int input;
	scanf("%d",&input);
	
  while(input > 1){
		if(input % 2 == 0)
			input /= 2;
		else
			input = -1;
	}
	if(input == 1)
		printf("Yes\n");
	else
		printf("No\n");
	
}

// runtime error가 나온다. 
// 그 말인 즉슨, 재귀 과정에서 너무 많이 내려갈 수가 있다는 것이다. 
// 비트마스크를 이용할 수 있지 않을까?
// 32

알고보니 10^18이라 int가 아닌 long long으로 데이터 타입을 맞춰줘야 했다. 

이렇게 반복문으로 푸는 것 말고 비트마스크를 이용하여 푸는 방법도 있다.

#include <iostream>
using namespace std;
int main() {
	long long num;
	cin >> num;
	if(num == (num & (-num)))
		cout << "Yes";
	else
		cout << "No";
}

난 num & (-num) 이 부분이 이해가 안된다. 내일 나의 멘토에게 물어볼 생각이다.