给定一个由 0, 1, 2, 3 · · · 的二进制表示拼接而成的长度无限的 01 串。
其前若干位形如 011011100101110111 · · · 。
请求出这个串的前 x 位里有多少个 1 。
输入的第一行包含一个正整数 x 。
输出一行包含一个整数表示答案。
7
5
【样例说明】
给定的串的前 7 位为 0110111 。
【评测用例规模与约定】
对于 60% 的评测用例，x ≤ 106 ；
对于所有评测用例，1 ≤ x ≤ 1018 。