1290. Shifting by the Whole Width
A 32-bit pattern u, from 0 to 4294967295, is to be shifted LEFT by k, and
k may be anything from 0 to 64. The answer is DEFINED as follows: bits shifted
past bit 31 fall off the end, so when k is 32 or more the answer is 0. Print
the result as an unsigned 32-bit value.
1 0 -> 1
1 31 -> 2147483648
1 32 -> 0
255 24 -> 4278190080
255 25 -> 4261412864 the top bit of 255 has fallen off
## What most people try first
(u << k) & 0xFFFFFFFF and nothing else. The mask is right and the shift is the
problem, because at k >= 32 the expression is not merely wrong, it has no
agreed meaning:
C and C++ shifting a 32-bit value by 32 or more is UNDEFINED BEHAVIOUR. Not
"gives zero", not "gives the value back": the compiler may assume it
never happens and optimise the surrounding code on that basis.
Java << uses k mod 32 on an int, so 1 << 32 is 1 and 1 << 33 is 2.
JavaScript the same, because << coerces to a 32-bit shift: 1 << 32 is 1. This
was run to confirm.
Python correct, because its integers have no width.
So three of the five languages give 1 where the required answer is 0, and
one of those three is allowed to do something far worse than give a wrong
number.
## The fix is a guard, not a wider type
if k >= 32: answer = 0
else: answer = (u << k) & 0xFFFFFFFF
The guard has to come FIRST. Widening to 64 bits and shifting there works for
k up to 63 and moves the cliff rather than removing it; at k = 64 the same
undefined shift reappears. A guard is the only version that is correct for every
k the constraints allow, which is why the constraint deliberately goes up to
64 rather than stopping at 63.
## Why the mask is still needed when k is small
With k = 24 and u = 255, the true 32-bit answer is 4278190080. Computed in
a 64-bit type without the mask, 255 << 24 is also 4278190080, so the mask
looks redundant. With k = 25 the 64-bit value is 8556380160, and the 32-bit
answer is 4261412864: the top bit of 255 has moved past bit 31 and must
disappear. The mask is what makes it disappear. Both of those are declared
tests, next to each other, for that reason.
## Width
The pattern and the answer are both unsigned 32-bit values, from 0 to
4294967295. That does not fit in a signed 32-bit integer, whose limit is
2147483647, so the reference solutions hold the value in a 64-bit integer and
mask down to 32 bits. The shift amount is at most 64 and never applied as a
shift, only compared.
In JavaScript the value does not fit in the 31 value bits << offers, and the
operator would additionally reduce k modulo 32, so the reference uses
BigInt: (BigInt(u) << BigInt(k)) & 0xFFFFFFFFn under the same k < 32
guard. Using u * Math.pow(2, k) instead would reach 2^63 and pass
2^53 = 9007199254740992, where a Number is no longer exact, so arithmetic is
not a way out here.
Constraints - `1 ≤ q ≤ 100000` - `0 ≤ u ≤ 4294967295` - `0 ≤ k ≤ 64`
Input
The first line contains an integer q.
Each of the next q lines contains two integers u and k, separated by a space.
Output
For each line print one integer on its own line: the pattern shifted left by k inside 32 bits, as an unsigned value from 0 to 4294967295. Print 0 whenever k is 32 or more.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.