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:
Interesting Array
Gray code
Ordering T-Shirts
Reach Median
Yet Another Array Queries Problem
Purification
Parity
Lost Array
Producing Snow
Berland Miners
Businessmen Problems
Bacterial Melee
Merging Two Decks
Perfect Security
New Year and the Christmas Ornament
Bear and Contribution
Clique in the Divisibility Graph
Triangle
Bob and stages
Height All the Same
Wheels
Competitive Programmer
Alice and Hairdresser
Sharti
Adding Powers
Molly's Chemicals
Bonus Distribution
Second best Minimum Spanning Tree - Using Kruskal and Lowest Common Ancestor
Falling Blocks
Captain Marmot
Nastya and Strange Generator
New Year Permutation