1295. Swapping Two Bits of a Value
For each of q triples x i j, print x with the bits at positions i and
j exchanged. The positions may be equal, in which case nothing changes.
5 0 1 -> 6 101 becomes 110
5 0 2 -> 5 both bits are 1, so nothing changes
5 1 2 -> 3 101 becomes 011
## What most people try first
Read both bits, clear both positions, then write each bit back at the other position:
bi = (x >> i) & 1
bj = (x >> j) & 1
x = x & ~(1 << i) & ~(1 << j)
x = x | (bi << j) | (bj << i)
That is correct, and it is four masks and two shifts of work for something one
XOR does. It is also where the i == j case tends to break if the clearing and
the writing are reordered.
## When the bits differ, XOR both positions
If the two bits are EQUAL, swapping them changes nothing. If they DIFFER, then swapping them is the same as flipping both, because flipping a 0 gives the 1 that belongs there and flipping the 1 gives the 0:
if ((x >> i) & 1) != ((x >> j) & 1):
x = x ^ ((1 << i) | (1 << j))
So the whole operation is one comparison and, at most, one XOR against a two-bit mask.
## Why the equality test cannot be dropped
XORing unconditionally flips both bits, which is only a swap when they differ.
On x = 5 = 101 with i = 0 and j = 2 both bits are 1, the correct answer is
5, and the unconditional version gives 101 XOR 101 = 0. That input is a
declared sample for exactly this reason.
The condition can be written more compactly as
((x >> i) ^ (x >> j)) & 1, which is non-zero exactly when the two bits
disagree. It is the same test.
## The equal-positions case
When i == j the two bits are trivially equal, so the comparison is false and
nothing happens, which is correct with no special case. Note that the
unconditional XOR version is ALSO correct here, since
(1 << i) | (1 << i) is a single bit and XORing it twice cancels, but it is
correct by accident rather than by argument.
## Width
Values reach 10^18, below 2^60, and positions run from 0 to 59, so every
value and every mask fits in a signed 64-bit integer, limit
9223372036854775807. A signed 32-bit integer cannot hold the input.
The masks are the width hazard: 1 << i with i up to 59 must be written
1ULL << i in C and C++ and 1L << i in Java, because a plain 1 is an
int and the shift happens in 32 bits before any widening. In JavaScript <<
and ^ coerce to signed 32 bits, so the reference uses BigInt.
Constraints - `1 ≤ q ≤ 100000` - `0 ≤ x ≤ 1000000000000000000` - `0 ≤ i ≤ 59` and `0 ≤ j ≤ 59`
Input
The first line contains an integer q.
Each of the next q lines contains three integers x, i and j, separated by spaces.
Output
For each triple print one integer on its own line: the value of x after exchanging the bits at positions i and j.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.