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:
Pudding Monsters
Memory for Arrays
Kay and Eternity
Yuhao and a Parenthesis
Fox And Names
Bulbo
The Art of Dealing with ATM
MP3
Rectangles and Square
Finding repetitions
Tree and XOR
Cube Problem
Diverse Permutation
Gena and Second Distance
Nastya and Unexpected Guest
Suns and Rays
Finding the Eulerian path in $O(M)$
T-shirt buying
GCD Table
Property
Jerry's Protest
Finding Power of Factorial Divisor
Rectangle Painting 1
Finding strongly connected components - Building condensation graph
Level Statistics
Second best Minimum Spanning Tree - Using Kruskal and Lowest Common Ancestor
Maximum flow - MPM algorithm
Chaotic V.
Booking System
Suffix Array
Petr and a Combination Lock
Social Network