Hoarding programming problems for you!

Looking for good programming challenges?

Use the search below to find our solutions for selected questions!

Sum vs XOR

Sharing is caring!

Problem Statement
Given an integer, n, find each x such that:

0 \le x \le n
n + x = n \oplus x

where \oplus denotes the bitwise XOR operator. Then print an integer denoting the total number of x‘s satisfying the criteria above.

Input Format
A single integer, n.

0 \le n \le 10^{15}

Output Format
Print the total number of integer x‘s satisfying both of the conditions specified above.

Sample Input

Sample Output


For n=5, the x values 0 and 2 satisfy the conditions:

5 + 0 = 5 \oplus 0 = 5
5 + 2 = 5 \oplus 2 = 7

Thus, we print 2 as our answer.