题目描述

给定一个由 $0, 1, 2, 3 \dots$ 的二进制表示拼接而成的长度无限的 $01$ 串。其前若干位形如 $011011100101110111\dots$。

请求出这个串的前 $x$ 位里有多少个 $1$。

输入格式

输入的第一行包含一个正整数 $x$。

输出格式

输出一行包含一个整数表示答案。

7

5

提示

样例说明

给定的串的前 $7$ 位为 $0110111$。

评测用例规模与约定

• 对于 $60\%$ 的评测用例，$x \leq 10^6$；
• 对于所有评测用例，$1 \leq x \leq 10^{18}$。