题目描述

给定一个整数 $n$，请问从 $1$ 开始到 $n$ 结束的所有整数的二进制表示中，共计有多少个 1 ？

输入格式

• 单个整数表示 $n$

输出格式

• 单个整数表示答案

12

22

数据范围

• $30\%$ 的数据，$1\leq n\leq 2^{10}$
• $60\%$ 的数据，$1\leq n\leq 2^{20}$
• $100\%$ 的数据，$1\leq n\leq 2^{50}$