D - Caracal vs Monster /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 400

問題文

カラカルはモンスターと戦っています。

モンスターの体力は H です。

カラカルはモンスターを 1 体選んで攻撃することができます。モンスターを攻撃したとき、攻撃対象のモンスターの体力に応じて、次のどちらかが起こります。

  • モンスターの体力が 1 なら、そのモンスターの体力は 0 になる
  • モンスターの体力が X >1 なら、そのモンスターは消滅し、体力が \lfloor X/2 \rfloor のモンスターが新たに 2 体現れる

\lfloor r \rfloorr を超えない最大の整数を表す)

全てのモンスターの体力を 0 以下にすればカラカルの勝ちです。

カラカルがモンスターに勝つまでに行う攻撃の回数の最小値を求めてください。

制約

  • 1 \leq H \leq 10^{12}
  • 入力中のすべての値は整数である。

入力

入力は以下の形式で標準入力から与えられる。

H

出力

カラカルがモンスターに勝つまでに行う攻撃の回数の最小値を出力せよ。


入力例 1

2

出力例 1

3

モンスターを攻撃すると、元のモンスターは消滅し、体力 1 のモンスターが 2 体現れます。

この 2 体のモンスターをそれぞれ 1 回ずつ攻撃し、合計 3 回の攻撃で勝つことができます。


入力例 2

4

出力例 2

7

入力例 3

1000000000000

出力例 3

1099511627775

Score : 400 points

Problem Statement

Caracal is fighting with a monster.

The health of the monster is H.

Caracal can attack by choosing one monster. When a monster is attacked, depending on that monster's health, the following happens:

  • If the monster's health is 1, it drops to 0.
  • If the monster's health, X, is greater than 1, that monster disappears. Then, two new monsters appear, each with the health of \lfloor X/2 \rfloor.

(\lfloor r \rfloor denotes the greatest integer not exceeding r.)

Caracal wins when the healths of all existing monsters become 0 or below.

Find the minimum number of attacks Caracal needs to make before winning.

Constraints

  • 1 \leq H \leq 10^{12}
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

H

Output

Find the minimum number of attacks Caracal needs to make before winning.


Sample Input 1

2

Sample Output 1

3

When Caracal attacks the initial monster, it disappears, and two monsters appear, each with the health of 1.

Then, Caracal can attack each of these new monsters once and win with a total of three attacks.


Sample Input 2

4

Sample Output 2

7

Sample Input 3

1000000000000

Sample Output 3

1099511627775