Given an integer, \(n\), find each \(k\) such that:

- \(0\leq k\leq n\)
- \(n+k=n\oplus k\)

where \(\oplus\) denotes the bitwise XOR operator. Then print an integer denoting the total number of \(k\)'s satisfying the criteria above.

**Input Format**

A single integer, \(n\).

**Constraints**

- \(0\leq n\leq 10^{15}\)

**Subtasks**

- \(0\leq n\leq 100\) for \(60\%\) of the maximum score.

**Output Format**

Print the total number of integer \(k\)'s satisfying both of the conditions specified above.

## Solution

The core of this question addresses the way a half-adder works. A one bit addition in fact is XOR. The underlaying problem for this question is then to find out when a carry over happens, since this will change the result completely, which states that \(n + k=n\oplus k\) only holds for \(n\land k = 0\). We can also say that \(n+k=n\oplus k\Leftrightarrow n+k=n\lor k\), since \(n+k\geq n\lor k=n\oplus k+n\land k\). That means that all operands that are 1 in the bit vector \(n\) must be 0 in \(k\). The bits in \(n\) don't change, but \(k\) can take on 0 or 1. And that implies that all we need to do is counting the number of zeros in the bit vector \(n\), since they give answer to carry overs and how a combination with \(k\) will affect the result. Counting the number of unset bits can be accomplished with

\[\lfloor 1+\log n\rfloor - \sum\limits_{i=0}^{\lfloor \log n\rfloor} n_i = \sum\limits_{i=0}^{\lfloor \log n\rfloor} (1-n_i)\]

Implementing this mathematical derivation as a naive routine gives

```
def countZeroBits(n)
c = 0;
while n > 0
c+= 1 - (n & 1)
n>>= 1
end
return c
end
```

Okay, having the number of unset bits, how does this help? Since we want all numbers \(k\) for the criterion, it means that we need all possible permutations, leading to \(2^c\) being the solution:

```
def solve(n)
1 << countZeroBits(n)
end
n = gets.strip.to_i
result = solve(n)
puts result
```