CF959E Mahmoud and Ehab and the xor-MST

Ehab 对按位异或运算和特殊图很感兴趣。Mahmoud 给了他一个结合了这两者的问题。他有一个包含 $n$ 个顶点的完全图，顶点编号从 $0$ 到 $n-1$。对于所有 $0 \leq u < v < n$，顶点 $u$ 和顶点 $v$ 之间有一条无向边，边的权值为 $u \oplus v$（其中 $\oplus$ 表示[按位异或运算](https://en.wikipedia.org/wiki/Bitwise_operation#XOR)）。你能求出该图的最小生成树的权值吗？ 你可以在 [https://en.wikipedia.org/wiki/Complete_graph](https://en.wikipedia.org/wiki/Complete_graph) 阅读关于完全图的内容。 你可以在 [https://en.wikipedia.org/wiki/Minimum_spanning_tree](https://en.wikipedia.org/wiki/Minimum_spanning_tree) 阅读关于最小生成树的内容。 最小生成树的权值是其包含的所有边的权值之和。

输入仅一行，包含一个整数 $n$，表示图中顶点的数量，$2 \leq n \leq 10^{12}$。

输出仅一行，包含一个整数 $x$，表示该图的最小生成树的权值。

在第一个样例中： 下图所示，最小生成树的权值为 $1+2+1=4$。 由 ChatGPT 4.1 翻译