해밍 거리

두 정수의 해밍 거리란, 각각을 이진수로 나타내었을 때 비트가 서로 다른 위치의 개수를 의미한다.

예를 들어, $9$와 $12$의 해밍 거리를 구해 보자.

$$ \begin{aligned} 9 &= 1001_{(2)} \\ 12 &= 1100_{(2)} \end{aligned} $$

$2^0$의 자리와 $2^2$의 자리에서 비트가 서로 다르므로 해밍 거리는 $2$이다.

두 수의 자릿수가 다르다면 상위 비트에 $0$을 붙여서 비교한다. 예를 들어, $3$과 $11$의 해밍 거리를 구해 보자.

$$ \begin{aligned} 3 &= 0011_{(2)} \\ 11 &= 1011_{(2)} \end{aligned} $$

$2^3$의 자리에서 비트가 서로 다르므로 해밍 거리는 $1$이다.

$A$ 이상 $B$ 이하의 정수 중에서, 해밍 거리가 최대인 두 정수를 구하시오.

정수 $A$와 $B$가 공백으로 구분되어 주어진다. $(1 \le A < B \le 10^{18})$

$A$, $B$가 32비트 정수 범위를 넘을 수 있음에 주의하라.

$A$ 이상 $B$ 이하의 정수 중에서, 해밍 거리가 최대인 두 정수를 공백으로 구분하여 출력한다.

그러한 정수 쌍이 여러 개라면 그중 아무거나 하나만 출력한다.

첫 번째 예제의 출력을 이진수로 나타내면 다음과 같다.

$$ \begin{aligned} 6 &= 0110_{(2)} \\ 9 &= 1001_{(2)} \end{aligned} $$

각 위치의 비트를 비교했을 때 서로 다른 비트의 수는 $4$개이므로 해밍 거리는 $4$이며, 이것이 최대이다.

두 번째 예제의 출력을 이진수로 나타내면 다음과 같다.

$$ \begin{aligned} 29 &= 11101_{(2)} \\ 26 &= 11010_{(2)} \end{aligned} $$

각 위치의 비트를 비교했을 때 서로 다른 비트의 수는 $3$개이므로 해밍 거리는 $3$이며, 이것이 최대이다.