Two positive integers a and b have a sum of s and a bitwise XOR of x. How many possible values are there for the ordered pair (a, b)?
Input
The first line of the input contains two integers s and x (2 ≤ s ≤ 1012, 0 ≤ x ≤ 1012), the sum and bitwise xor of the pair of positive integers, respectively.
Output
Print a single integer, the number of solutions to the given conditions. If no solutions exist, print 0.
Examples
input
9 5
output
4
input
3 3
output
2
input
5 2
output
0
Note
In the first sample, we have the following solutions: (2, 7), (3, 6), (6, 3), (7, 2).
In the second sample, the only solutions are (1, 2) and (2, 1).
Solution:
#include <bits/stdc++.h> using namespace std; int main() { long long sum, x; cin >> sum >> x; long long a = (sum - x) / 2; if (a < 0 || x + 2 * a != sum || (x & a) != 0) { cout << 0 << endl; return 0; } long long bits = 0; long long tmp = x; while (tmp > 0) { bits += tmp & 1; tmp >>= 1; } long long ans = 1LL << bits; if (a == 0) { ans -= 2; } cout << ans << endl; return 0; }
Related posts:
Au Pont Rouge
Felicity's Big Secret Revealed
Parallel Programming
Xenia and Hamming
Bear and Two Paths
Berland Federalization
Segment Tree
Wheels
Bombs
Om Nom and Candies
Tourism
Kaavi and Magic Spell
Rational Resistance
Dima and Figure
Superhero's Job
PE Lesson
Bags and Coins
Pudding Monsters
Sieve of Eratosthenes
Hongcow Masters the Cyclic Shift
Elections
Little Artem and Time Machine
New Year Letter
New Year Ratings Change
Sereja and Algorithm
Cunning Gena
Divide by three, multiply by two
Traveling Around the Golden Ring of Berland
Topological Sorting
Finding Bridges Online
Counting labeled graphs
Ordering T-Shirts