# 题目描述

​Xhescia 首先需要知道事情一共有多少种发展的可能情况。

​经过 Xhescia 的计算，总的情况数为以下方程的非负整数解的数量。

$$a \vee x = a$$

​其中 $x$ 为未知数，$a$ 为给定的非负整数。$\vee$ 代表按位或。

现在，你来帮 Xhesica 算一算吧。

# 输入格式

一行，一个数字 $a$，满足 $1 \le a \le 10^{18}$

# 输出格式

一行，一个整数。

# 输入样例

1

# 输出样例

2

# 样例解释

$x$ 可以取 $0$ 或者 $1$。

# 题解：位运算

考虑按位或的特点：如果一个数是 $1$，那么结果一定是 $1$。

于是我们将 $a$ 的二进制拆开，按位依次考虑。如果这一位是 $1$，那么 $x$ 这一位可取 $0$ 也可取 $1$，因为这一位或出来的结果都是 $1$；如果这一位是 $0$，那么 $x$ 这一位只能取 $0$，才能保证或出来的结果是 $0$。

由于按位或对每一位的运算是独立的，我们把 $x$ 每一位可能的取值情况相乘即可得到答案，即答案为 $2^{\mathrm {popcount} (a)}$，其中 $\mathrm {popcount} (a)$ 表示 $a$ 在二进制表示下有多少位为 $1$。

时间复杂度为 $O(\log a)$。

参考代码：

#include <stdio.h>

typedef long long ll;

ll a;

int main()

{

    // freopen("A.in", "r", stdin);

    // freopen("A.out", "w", stdout);

    scanf("%lld", &a);

    int cnt = 0;

    while (a)

    {

        cnt += a & 1;

        a >>= 1;

    }

    printf("%lld\n", 1ll << cnt);

    return 0;

}