[BAE/<JOON> 문제풀이] 1322. X 와 K

https://www.acmicpc.net/problem/1322

1322번: X와 K

핵심::
비트 연산 구현 문제

풀이::
X | Y = X + Y 는 X와 Y를 2진수로 변환 했을 때 각 자리가 모두 다르다는 것을 의미한다.

따라서 주어진 X에 대해서 2진수 Y가 1을 사용할 수 있는 자리는 정해져 있다.

X와 K의 최댓값은 2,000,000,000 이므로 계산해보면 2진수의 최대 자리수는 31자리 이다.

X의 최댓값 2진수는 31자리이므로 그보다 큰 2 * 10^9 번째 수는 2^31 + (2 * 10^9) * 2^32 이다.

하지만 모든 자리가 1이어야 31자리 이상의 자릿수에서 1이 나올 수 있으므로 고려해야하는 최대 자릿수는 

31자리 2진수 + 31자리 2진수 - 1 = 61자리 이다. -1은 X의 최댓값일 경우 모든 자리가 1일 수 없기 때문이다.

X가 2 ^ 31 - 1 일 때 30자리로 가장 많은 1을 사용할 수 있다.

X를 2진수로 변환하며 자리의 숫자가 0인 지점들을 미리 1을 사용할 수 있는 지점에 저장한다.

나머지 61자리까지도 1을 사용할 수 있는 지점에 저장한다. ( 처음에 이 부분을 생각을 못해서 많이 틀렸다. 주어진 X의 앞부분에도 1이 들어갈 수 있다. )

이후 K를 2진수로 변환하여 X의 숫자가 0인 지점에 그대로 삽입하면 된다.

EX) 
X = 10, K = 6
이진수로 바꾸면 X = 1 0 1 0, K = 1 1 0
X에 ~0, 1, 3번째 자릿수에 1 삽입 가능
-> 1 1 1 1 0 = 30

의견::
헷갈림 코드 짤때는 정확한 자릿수 계산 없이 대충 최대 70자리로 작성함

코드::

#include <iostream>
#include <cmath>
#include <vector>

using namespace std;

int main()
{
	int n, k; cin >> n >> k;
	int j = n;
	int cnt = 0;
	vector<int> list;
	while (j > 0) {
		if (j % 2 == 0) {
			list.push_back(cnt);
		}
		j /= 2;
		cnt++;
	}

	for (; cnt <= 70; cnt++) {
		list.push_back(cnt);
	}

	j = k;
	unsigned long long sum = 0;
	cnt = 0;
	while (j > 0) {
		if (j % 2 == 1) {
			sum += ((unsigned long long)1 << list[cnt]);
		}
		cnt++;
		if (cnt >= list.size()) break;
		j /= 2;		
	}

	cout << sum;
	return 0;	
}