题目背景

翻译自 CSES-1146 题。

题目描述

你的任务是计算从 $1$ 到 $n$ 之间的所有整数的二进制表示中 $1$ 的个数。

输入格式

输入的唯一一行包含一个整数 $n$。

输出格式

输出从 $1$ 到 $n$ 之间所有整数的二进制表示中 $1$ 的个数。

样例

7

12

提示

从 $1$ 到 $7$ 的整数的二进制表示分别是：

• $1 = 1$
• $2 = 10$
• $3 = 11$
• $4 = 100$
• $5 = 101$
• $6 = 110$
• $7 = 111$

这些二进制表示中共有 $12$ 个 $1$，因此输出 $12$。

数据范围

• $1 \le n \le 10^{15}$