给定一个由 0, 1, 2, 3 · · · 的二进制表示拼接而成的长度无限的 01 串。

其前若干位形如 011011100101110111 · · · 。 

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

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

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

7

5

【样例说明】 

给定的串的前 7 位为 0110111 。 

【评测用例规模与约定】 

对于 60% 的评测用例，x ≤ 10⁶ ； 

对于所有评测用例，1 ≤ x ≤ 10¹⁸ 。