P12191 [蓝桥杯 2025 省研究生组] 01 串

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

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

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

### 样例说明 给定的串的前 $7$ 位为 $0110111$。 ### 评测用例规模与约定 - 对于 $60\%$ 的评测用例，$x \leq 10^6$； - 对于所有评测用例，$1 \leq x \leq 10^{18}$。