627A - XOR Equation

8VC Venture Cup 2016 — Final Round A번 문제이다. (Div.1 Edition B번, Div.2 Edition C번)

별로 어렵지 않은 문제인데 한참동안 해매어서 정리.

두 양의 정수 a와 b의 합이 s이고 XOR한 결과가 x일 때에, 가능한 (a, b) 순서쌍의 개수를 구하는 것이 문제이다.

접근법 1)

a+b = s, a^b = x

b = (s-a)

a^(s-a) = x

s-a = a^x. 양번에 a를 XOR하면 a^(s-a) = a^x

여기서 잘못됨을 깨닫고 다른 관계식을 시도함.

접근법 2)

a^b = a+b - 2(a&b)

XOR라는 연산이 두 bit가 다르면 1이기 때문에 덧셈에서 자리올림을 빼면 그 결과가 XOR와 같다는 식.

정리하면 (s-x)/2 = a&b

여기서 매 digit마다 (s-x)/2는 상수이기 때문에 a&b의 결과를 가지고 a와 b에 대해 생각해보면,

i) a&b = 1 : a = b = 1, 1가지 가능한 경우.

따라서 a^b는 0이 되어야한다.

ii) a&b = 0

a^b = 1 : a = 0, b = 1 / a = 1, b = 0, 2가지 가능한 경우.

a^b = 0 : a = b = 0, 1가지 가능한 경우.

마지막으로, 두 양의 정수 a와 b이기 때문에 a = 0이거나 b = 0이 되는 2가지 경우를 빼주면 된다.

내 코드는 아래와 같은데

#include <iostream>
using namespace std;
typedef long long ll;
ll s, x, d, res = 1;
int main() {
	cin >> s >> x;
	if ((s - x) & 1) {
		puts("0");
		return 0;
	}
	d = (s - x) / 2;
	for (ll i = 0; i < 50; i++) {
		ll bit = (1LL << i);
		if (d & bit) {
			if (x & bit) {
				res = 0;
				break;
			}
		}
		else {
			if (x & bit)
				res *= 2LL;
		}
	}
	if (res > 0 && d == 0) res -= 2;
	cout << res;
}

어떤 bit끼리 & 연산한 결과가 양수이거나 0이거나인데, 1이거나 0이거나로 착각한 걸 고치는데 오래 걸렸음ㅋㅋ 이런 실수는 대회 때 절대 해서는 안되겠다.