Programming interview questions

Looking for good programming/interview questions?

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.