Robert Eisele
Engineer, Systems Architect and DBA

# Hackerrank: Sum vs XOR

Original Problem

Given an integer, $$n$$, find each $$k$$ such that:

• $$n\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}$$

• $$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

« Back to problem overview