C - 趣味二进制

时空限制

• CPU占用时长: 1秒
• 内存使用限制: 128MB

题目描述

如果一个整数的二进制表示是连续若干个 "$1$" 后紧跟着连续若干个 "$0$"，我们将这类数称为"趣味二进制"数。例如，十进制数 $12$ 的二进制表示为 $1100$，$16$ 的二进制表示为 $10000$，它们都是趣味二进制数。但 $7$ 的二进制表示只含连续 $1$ 但不含 $0$ 就不属于"趣味二进制"数。

在十进制数 $1, 2, \ldots, n$ 之间，有多少个这样的趣味二进制数呢？

输入格式

输入一行，一个正整数 $n$。

输出格式

输出一行，一个整数，表示趣味二进制数的个数。

输入输出样例

样例 1

输入：

12

输出：

5

样例说明

$1, 2, \ldots, 12$ 中的趣味二进制数分别是 $2, 4, 6, 8, 12$。

样例 2

输入：

16384

输出：

92

数据范围与提示

• 对于 $60\%$ 的数据，有 $n \le 100000$。
• 对于 $100\%$ 的数据，有 $1 \le n \le 1000000000$。