题目描述

设 $\operatorname{Xor}$ 为二进制异或操作，$\operatorname{popcount}$ 为统计某数在二进制下 $1$ 的个数。

给定 $n$，求：

$$\sum_{i=1}^n \operatorname{popcount}((i-1)\operatorname{Xor} i) $$

输入格式

一行一个正整数表示 $n$。

输出格式

一行一个整数表示对答案。

样例 #1

样例输入 #1

11

样例输出 #1

19

样例 #2

样例输入 #2

2000000000000

样例输出 #2

3999999999987

提示

• 对于 $30\%$ 的数据，有 $n\le 10^6$
• 对于 $50\%$ 的数据，有 $n\le 10^8$
• 对于 $70\%$ 的数据，有 $n\le 10^{10}$
• 对于全部 $100\%$ 的数据，有 $n\le 10^{18}$