h265. 折半累加

题目描述

定义函数 $F$：

• $F(0)=0$；
• 当 $n>0$ 时，$F(n)=n+F(\lfloor n/2\rfloor)$。

给定 $n$，求 $F(n)$。

输入格式

输入一个整数 $n$。

输出格式

输出 $F(n)$ 的值。

数据范围

• $0\le n\le 1000000000$
• 答案小于 $2000000000$。

样例

输入

10

输出

18

标签：递归、递推、整数除法