Codeforces 959 E Mahmoud and Ehab and the xor-MST

Discription

Ehab is interested in the bitwise-xor operation and the special graphs. Mahmoud gave him a problem that combines both. He has a complete graph consisting of n vertices numbered from 0 to n - 1. For all 0 ≤ u < v < n, vertex u and vertex v are connected with an undirected edge that has weight  (where  is the bitwise-xor operation). Can you find the weight of the minimum spanning tree of that graph?

You can read about complete graphs in https://en.wikipedia.org/wiki/Complete_graph

You can read about the minimum spanning tree inhttps://en.wikipedia.org/wiki/Minimum_spanning_tree

The weight of the minimum spanning tree is the sum of the weights on the edges included in it.

Input

The only line contains an integer n (2 ≤ n ≤ 10¹²), the number of vertices in the graph.

Output

The only line contains an integer x, the weight of the graph's minimum spanning tree.

Example

4

4

Note

In the first sample: The weight of the minimum spanning tree is 1+2+1=4.

    依次考虑加入边权 1,2.....的边，看能否使图的连通性产生变化。

发现只有 2^i 的边能对图的连通性产生变化，并且有用的边的数量也很好计算 (不妨画一个图就能很快的发现这个规律)，所以就可以直接 递归/迭代 做了。

#include<bits/stdc++.h>
#define ll long long
using namespace std;
inline ll LB(ll x){ return x&-x;}
ll solve(ll x){
	return x==1?0:(solve(x>>1)*2ll+(x>>1)+((x&1)?LB(x-1):0));
}
int main(){
	ll n; scanf("%I64d",&n);
	printf("%I64d
",solve(n));
	return 0;
}