1289. Arithmetic and Logical Right Shift Side by Side
A 32-bit pattern is given as an unsigned value u, from 0 to 4294967295, with
a shift amount k from 0 to 31. Print the result of shifting it right TWO
ways:
arithmetic: treat the pattern as a SIGNED 32-bit integer, shift right, and
print the result as a signed integer. The vacated top bits are
filled with copies of the original sign bit.
logical: treat the pattern as UNSIGNED, shift right, and print the result
as an unsigned integer. The vacated top bits are filled with 0.
Print the arithmetic result first, then the logical one.
16 2 -> 4 4 positive, so the two agree
4294967295 1 -> -1 2147483647 all ones, so they disagree completely
2147483648 31 -> -1 1 the sign bit alone
## What most people try first
Assuming there is one right shift. There are two, and which one >> means
depends on the language and on the type:
C and C++ >> on an UNSIGNED type is logical. On a SIGNED NEGATIVE value it is
implementation-defined: every real compiler makes it arithmetic,
and the standard does not require it.
Java >> is arithmetic and >>> is logical. Two operators, no ambiguity.
JavaScript >> is arithmetic and >>> is logical, both on a signed 32-bit
coercion of the operand.
Python >> is arithmetic on integers that have no width at all, so there is
no logical shift to speak of and a 32-bit one must be emulated.
That is five languages and four different stories, which is why this problem
asks for both answers explicitly instead of letting >> decide.
## Why the two differ, and when they do not
A right shift divides by 2^k. For a non-negative value both shifts give the
same thing, because the vacated bits are zero either way. For a NEGATIVE value
the arithmetic shift keeps the sign by copying the sign bit down, so the result
stays negative and equals floor(x / 2^k); the logical shift inserts zeros, so
the result is a large positive number instead.
pattern 4294967295 = 1111...1111 is -1 as a signed value
>> 1 arithmetic = 1111...1111 still -1
>> 1 logical = 0111...1111 = 2147483647
So the first declared sample agrees and the second disagrees as widely as two answers can.
## Why k stops at 31
Shifting a 32-bit value by 32 or more is UNDEFINED in C and C++, uses
k mod 32 in Java, and also uses k mod 32 in JavaScript. There is no answer
all five languages agree on, so the constraint forbids it rather than inventing
one. #1290 is the problem about exactly that case, and it guards it instead of
shifting.
## Width
Everything is 32 bits. The pattern runs to 4294967295, which is 2^32 - 1
and does NOT fit in a signed 32-bit integer, whose limit is 2147483647; so
the pattern is read into a 64-bit integer or an unsigned 32-bit one, and the
signed interpretation is computed from it. The arithmetic result runs from
-2147483648 to 2147483647 and the logical result from 0 to 4294967295.
JavaScript is safe with plain Numbers and is in fact the cleanest of the five
here: (u | 0) >> k is the arithmetic shift and u >>> k is the logical one.
Both were run. (4294967295 | 0) >> 1 gives -1 and 4294967295 >>> 1 gives
2147483647, which match the declared sample exactly.
Constraints - `1 ≤ q ≤ 100000` - `0 ≤ u ≤ 4294967295` - `0 ≤ k ≤ 31`
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 two integers on one line separated by a single space: the arithmetic right shift result, as a signed value, then the logical right shift result, as an unsigned value.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.