Mahmoud and Ehab와 xor-MST

Ehab은 비트 단위 xor 연산과 특수 그래프에 관심이 있다. Mahmoud는 이 둘을 결합한 문제를 그에게 주었다. 그는 0부터 n - 1까지 번호가 매겨진 n개의 정점으로 이루어진 완전 그래프를 가지고 있다. 모든 0 ≤ u < v < n에 대해, 정점 u와 정점 v는 가중치가 인 무방향 간선으로 연결되어 있다(여기서 는 bitwise-xor operation). 이 그래프의 최소 스패닝 트리의 가중치를 구할 수 있는가?

완전 그래프에 대해서는 https://en.wikipedia.org/wiki/Complete_graph에서 읽어 볼 수 있다.

최소 스패닝 트리에 대해서는 https://en.wikipedia.org/wiki/Minimum_spanning_tree에서 읽어 볼 수 있다.

최소 스패닝 트리의 가중치는 그 트리에 포함된 간선들의 가중치 합이다.

유일한 줄에 그래프의 정점 수를 나타내는 정수 n (2 ≤ n ≤ 1012)이 주어진다.

유일한 줄에 그래프의 최소 스패닝 트리의 가중치인 정수 x를 출력한다.

첫 번째 예제에서는 다음과 같다. 최소 스패닝 트리의 가중치는 1+2+1=4이다.