# Sum vs XOR, Bit manipulation problem

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

• 0<=x <=n
• n+x = n^ x

where ^  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.

Constraints

• 0<=n <=10**15

• 0<=n <=100 for 60% of the maximum score.

Output Format

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

Sample Input 0

5


Sample Output 0

2


Explanation 0

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

• 5 + 0 =  5 ^ 0 = 5
• 5 + 2 = 5 ^ 2 = 5

Thus, we print 2 as our answer.

Sample Input 1

10


Sample Output 1

4


Solution in PHP

If any problem, feel free to comment or contact.

This solution is totally a mathematical trick.

just count total numbers of ZERO present in binary number of given n, and answer will be the 2 to the power of (total num of zero).

Here one line solution
<?php
$handle = fopen ("php://stdin","r"); fscanf($handle,"%s",$n); echo ($n>0)?pow(2,substr_count(decbin($n),'0')):1;  This also same logic <?php$handle = fopen ("php://stdin","r");
fscanf($handle,"%d",$n);

$count=0; while($n>0){
$count += fmod($n,2) ? 0 : 1;
$n /=2;$n=floor($n); } echo pow(2,$count);

$handle = fopen ("php://stdin","r"); fscanf($handle,"%s",$n);$count=0;
while($n>0){$count += bcmod($n,2) ? 0 : 1;$n /=2;
$n=floor($n);
}
echo bcpow(2,\$count);