1300. Do They Differ in Exactly One Bit
For each of q pairs a b, print YES if the two values differ in exactly one
bit position and NO otherwise. A value does not differ from itself, so a pair
of equal values is NO.
0 1 -> YES 000 and 001
1 2 -> NO 001 and 010, two positions differ
5 7 -> YES 101 and 111
0 0 -> NO nothing differs
## What most people try first
Walking all 60 bit positions and counting the disagreements, stopping at two. That is correct and does up to 60 iterations per query, where one expression suffices.
## XOR marks the differences, and one bit means a power of two
a XOR b has a 1 in exactly the positions where a and b disagree, because
XOR is 1 precisely when its two inputs differ. So "differ in exactly one
position" means "a XOR b has exactly one bit set", and a value with exactly
one bit set is a power of two. That is #1249's test:
x = a XOR b
answer YES if x != 0 and (x & (x - 1)) == 0
The x != 0 guard is the whole subtlety and it is the same one #1249 needs. For
equal values x is 0, and 0 & (0 - 1) is also 0, so the expression alone
would report YES for every pair of identical values. The declared tests include
0 0 and a pair of equal large values for exactly that reason.
## The quantity this is measuring
The number of set bits in a XOR b is the HAMMING DISTANCE between the two
values, and this problem asks whether it is 1. That connects three things
already in this file: Gray code order, where consecutive entries are at Hamming
distance 1 by construction (#1298); popcount, which computes the distance in
general (#1246); and the power-of-two test, which recognises a distance of 1
without counting (#1249).
Asking for the full distance would need the popcount; asking only whether it is 1 does not, which is why this is the cheaper question.
## Width
Values reach 10^18, below 2^60, so a XOR b is also below 2^60 and
everything fits in a signed 64-bit integer, limit 9223372036854775807. A
signed 32-bit integer cannot hold the inputs, which stop at 2147483647.
In JavaScript ^ and & coerce to signed 32 bits, so the reference uses
BigInt. A Number version would compare only the low 32 bits of each value
and report YES for pairs that differ solely in a high bit, which is the worst
kind of wrong: plausible on small data and wrong on real data.
Constraints - `1 ≤ q ≤ 100000` - `0 ≤ a ≤ 1000000000000000000` and `0 ≤ b ≤ 1000000000000000000`
Input
The first line contains an integer q.
Each of the next q lines contains two integers a and b, separated by a space.
Output
For each pair print YES or NO on its own line, in upper case, with nothing else on the line.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.