들어가며 Candy Splitting (Large) 솔브드에서 제공하는 랜덤 마라톤에서 나온 문제입니다. XOR 연산에 대한 이해가 있어야 풀 수 있는 문제였습니다. 문제설명 형제 Sean과 Patrick은 부모님으로부터 캔디가 든 가방을 받았습니다. 가방 안에는 값이 다른 여러 개의 캔디가 들어있는데, 이를 공정한 방법으로 나누려고 합니다. Sean이 두 더미로 나누면 Patrick이 둘 중 하나를 골라 가져가는 방식이죠. 불행하게도 Patrick은 너무 어려서 캔디의 값을 올바르게 더하는 방법을 모릅니다. 대신 이진법 덧셈을 거의 할 줄 아는데, 올림을 까먹었습니다. 예를 들어, 12(1100), 5(101)이 있을 때 올바른 덧셈 결과는 17(10001)이지만, Patrick의 방식으로는 9(1001)

들어가며 알고리즘 문제를 풀다보면 boolean집합을 공간적으로 압축하기 위해 비트마스킹을 사용할 때가 종종 있습니다. [True, False, False, True, True, False, True, False]와 같은 배열을 10011010₂와 같이 표현하면 정수 하나로 표현 가능하기 때문이죠. 문제 중에는 정수의 특정 비트가 0인지 1인지 확인 해야 하거나 1의 개수를 세어야 할 경우 도 있습니다. 전자의 경우, 즉 특정 비트의 ON/OFF를 판단해야 하는 문제라면, ((임의의 정수) & (1 << n)) > 0와 같이 간단히 구할 수 있습니다. 오른쪽에서 n번째 비트가 1인 정수를 생성하고 임의의 정수와 AND 비트 연산을 하면, 다음과 같이 해당 비트가 1이라면 2^n, 아니라면 0을 결과로 산