1302. Reversing the Bits Within a Declared Width
For each of q pairs w x, reverse the bits of x within a field of width
w: bit 0 exchanges with bit w - 1, bit 1 with bit w - 2, and so on. Bits
at or above position w do not exist, since x is below 2^w.
w=4 x=1 -> 8 0001 becomes 1000
w=4 x=8 -> 1
w=4 x=5 -> 10 0101 becomes 1010
w=8 x=255 -> 255
## What most people try first
#1301's five-step mask cascade, with the result shifted down by 32 - w. That
works for w up to 32 and does not generalise: the masks are literals baked for
a 32-bit word, and for w = 63 there is no corresponding set of constants
without writing six more of them for 64 bits and then shifting down by 64 - w.
The deeper problem is that the cascade reverses a FIXED width. A declared width is a different question, and the answer is not a tuned cascade.
## Two pointers from the ends
lo = 0, hi = w - 1
while lo < hi:
if bit lo differs from bit hi:
x ^= (1 << lo) | (1 << hi)
lo = lo + 1
hi = hi - 1
Each iteration exchanges one pair, using #1295's observation that swapping two
bits is a two-bit XOR when they differ and nothing when they do not. The loop
runs w / 2 times, so at most 31 iterations.
The condition is lo < hi and not lo <= hi. When w is odd the middle
position has lo == hi and must be left alone; with lo <= hi that iteration
would XOR (1 << lo) | (1 << lo), which is a single bit, except that the
"differs from itself" test is false so nothing happens. So lo <= hi happens to
be harmless HERE, and it is harmless only because of the equality test. Relying
on that is how the bug gets in when someone later removes the test as an
optimisation.
## Why not shift the whole value
A tempting alternative is to build the answer by shifting bits out of x and
into a result:
r = 0
for i in 0 .. w-1:
r = (r << 1) | (x & 1)
x >>= 1
That is also correct and also O(w), and it is arguably clearer. It is in the
oracle as the brute force. The two-pointer version is given here because it
works IN PLACE, which matters when the value is a field inside a larger word and
cannot be rebuilt from scratch.
## Width
w is at most 63 and x is below 2^w, so values reach
2^63 - 1 = 9223372036854775807, exactly the limit of a signed 64-bit integer.
That is deliberate: it means the answer always fits as a SIGNED value and no
unsigned printing is needed, which keeps this problem about the reversal and
leaves the unsigned-output question to #1296. A signed 32-bit integer, limit
2147483647, cannot hold the inputs.
The shifts are the hazard. 1 << hi with hi up to 62 must be 1ULL << hi in
C and C++ and 1L << hi in Java, since a bare 1 is a 32-bit int and the
shift happens before any widening. In JavaScript the values pass
2^53 = 9007199254740992 and << coerces to 32 bits, so the reference uses
BigInt.
Constraints - `1 ≤ q ≤ 100000` - `1 ≤ w ≤ 63` - `0 ≤ x < 2^w`
Input
The first line contains an integer q.
Each of the next q lines contains two integers w and x, separated by a space.
Output
For each pair print one integer on its own line: the value of x with its bits reversed inside a field of width w.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.