/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 400 点
問題文
カラカルはモンスターと戦っています。
モンスターの体力は H です。
カラカルはモンスターを 1 体選んで攻撃することができます。モンスターを攻撃したとき、攻撃対象のモンスターの体力に応じて、次のどちらかが起こります。
- モンスターの体力が 1 なら、そのモンスターの体力は 0 になる
- モンスターの体力が X >1 なら、そのモンスターは消滅し、体力が \lfloor X/2 \rfloor のモンスターが新たに 2 体現れる
（\lfloor r \rfloor は r を超えない最大の整数を表す）
全てのモンスターの体力を 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