[Codeforces] Round 847 - Vlad and a Pair of Numbers

https://codeforces.com/contest/1790/problem/E

문제

$x = a \oplus b = {a + b\over 2}$ 를 만족하는 $a, b$ 찾기

풀이

xor 연산은 두 비트가 다를 때 1이므로,
$b = 0$이면 xor의 결과는 $a$의 값을 따르게 된다.

여기서 $a, b$ 에 같은 값을 더해주면 어떻게 될까?

[ before ]
a = 10110  (+1001)
b = 00000  (+1001)
===================
a xor b = 10110

[ after ] 
a = 11111
b = 01001
===================
a xor b = 10110

$a$와 $b$에 같은 값을 더했을 때, xor의 결과는 이전 결과와 똑같은 것을 확인할수 있다.
여기서 주의해야할 점이 하나 있는데, 같은 값을 더해줄 때 올림수가 발생하면 안된다는 것이다.

[ before ]
a = 10110  (+1011)
b = 00000  (+1011)
===================
a xor b = 10110

[ after ] 
a = 100001
b = 001011
===================
a xor b = 101010

위의 결과처럼 올림수가 발생했을 때, xor의 결과가 바뀐 것을 확인할 수 있다.
이 이유를 생각해보면 올림수가 발생을 하면서 이전 xor의 결과(=a)를 담당하던 비트가 달라졌기 때문이다.

이제 문제로 돌아와서 $a \oplus b = x$를 만족하는 $a = x, b= 0$에 대해서 생각해보자
이 경우에는 아직 ${a + b \over 2} = {x \over 2}\neq x$이므로 ${a + b \over 2} = x$를 만족하도록 같은 값인 ${x \over 2}$를 $a$와 $b$에 더해주면 된다.
(바로 위에서 설명했듯이 ${x \over 2}$를 더해줄 때, 올림수가 발생하면 안된다)

증명

올림수가 발생하지 않아야 한다는 점에서 납득이 가지 않을수도 있기 때문에 유도과정을 통해 증명해보자.

논리 연산에서 합 연산은 아래와 같이 표현할 수 있다.

처음에 설명했던 것처럼 $a = x, b=0$인 경우엔 xor와 sum의 결과는 같다.

이제 $a, b$에 각각 $x \over 2$를 더해줬을 때에도 xor와 sum이 같아야 한다.

#include <iostream>

using namespace std;

int main() {
	int T;
	cin >> T;

	while (T--) {
		int x;
		cin >> x;

		if (x % 2 == 1) { // 홀수면 right shift (x/2)에 손실 발생
			cout << -1 << "\n";
			continue;
		}

		int b = x >> 1; // b = x / 2
		if ((x & b) != 0) { // 올림수가 발생하는지 확인
			cout << -1 << "\n";
			continue;
		}
		
		cout << (x + b) << " " << b << "\n";
	}

	return 0;
}