F. 看程序写结果

传统题

1000ms

512MiB

该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

金鱼学习 C 语言的时间也不短了，但是看程序写结果的题目对他来说还是太棘手了。今天，金鱼又被一道看程序写结果的题目给难住了，你能帮帮金鱼吗？

难倒小Z的代码：

C/C++版：

long long f(long long x) {
    if (x == 1) return 1;
    return f(x / 2) + f(x / 2 + x % 2);
}

Python版：

def f(x):
    if x == 1:
        return 1
    return f(x // 2) + f(x // 2 + x % 2)

现在给出一个整数 $X$ ，请输出 $f(X)$ 的值。

输入一个正整数 $X(1\le X\le 10^{18})$ 。

输出一个整数，表示 $f(X)$ 的值。