【例题4】数位翻转

题目描述

设$g(x)$为将$x$的二进制表示进行翻转后得到的数。也就是如果$x$的二进制表示是$a_{1}$,$a_{2}$,$\ldots$,$a_{n}$（其中$a_{1}=1$），那么它翻转过来就是$a_{n}$,$a_{n-1}$,$\ldots$,$a_{1}$。例如$g(2)=1$，$g(6)=3$，$g(10)=5$。

设$cnt(x)$为$x$的二进制表示下$1$的个数。给定$R$，求$\sum_{i=1}^{R}cnt(i+g(i))$。

输入格式

第一行一个正整数$R$。

输出格式

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

数据范围与提示

• 对于$30\%$的数据，满足$1 \leq R \leq 10^{5}$；
• 对于$50\%$的数据，满足$1 \leq R \leq 10^{9}$；
• 另有$20\%$的数据，满足存在某个$i$使得$R = 2^{i}$；
• 对于$100\%$的数据，满足$1 \leq R \leq 10^{14}$。

样例

3

5

21312421

264774008