问题 1381. -- XOR

1381: XOR

时间限制: 1 Sec  内存限制: 128 MB
提交: 6  解决: 1
[提交][状态][讨论版]

题目描述

Once there was a king called XOR, he had a lot of land. Because of his name, he likes to play XOR games.

One day, he whimpered and wanted to establish N cities on that vast expanse of land, numbered 0, 1, 2..., N. He wanted to connect all the cities. If city A can reach City B through zero or one or several cities, then A and B are connected. The cost of repairing a road in City A and City B is the XOR value of number of City A and number of City B. This King XOR wanted to figure out the minimum cost for connecting all of the N cities.

Of course, like a fairy tale read as a child, there will be corresponding rewards after helping the king. If you help the king solve his problems, he will improve your ranking in the competition.

输入

The only line contains an integer N (2 ≤N≤ 20000), the number of cities the king wants to establish.

输出

The only line contains an integer x, the minimum cost for connecting all of the N cities.

样例输入

4

样例输出

4

提示

The weight of the minimum cost is 1+2+1=4 In the Sample Example.

来源

[提交][状态]