puzzle contents
raw puzzle

Original Problem

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\).


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


  • \(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.


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
  return c

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)

n = gets.strip.to_i
result = solve(n)
puts result