1282. Unpacking Whatever Layout You Are Handed
A record format declares n fields by WIDTH, lowest field first. Field 1 sits
at offset 0, field 2 immediately above it, and so on. Given q packed values,
print the fields of each, lowest first.
widths 10 10 10, value 1049603 -> 3 1 1
widths 8 8 8 8 8 8 8 4, value 1152921504606846975
-> 255 255 255 255 255 255 255 15
## What most people try first
Hard-coding the offsets, because the previous two problems had fixed layouts. A real record format is DECLARED, not known in advance: it comes from a header, a schema, a protocol specification. So the offsets must be derived from the widths at run time, and that derivation is the problem.
The other common move is to convert the value to a binary string and slice it. That works and it is a hundred times slower, it allocates per record, and it forces you to think about leading zeros and about which end of the string is bit 0. Getting the string direction wrong reverses every field.
## Offsets are a running total of widths
offset = 0
for each width w in order:
field = (v >> offset) & ((1 << w) - 1)
report field
offset = offset + w
Two things in that line are worth saying out loud.
(1 << w) - 1 is the mask for a w-bit field: 1 << w is a single bit at
position w, and subtracting one turns it off and every bit below it on, which
is exactly w ones. This is #1251's identity used forwards.
The shift comes BEFORE the mask. Masking first would need the mask shifted up to the field's position and then the result shifted down anyway, which is the same work in a less readable order. Shift down, then mask off what was above.
## Where this breaks if the widths are not checked
The widths are guaranteed here to sum to at most 60, so 1 << w is at most
1 << 60 and every offset is at most 60. Without that guarantee a declared
width of 64 would make 1 << 64 undefined behaviour in C and C++, and a
declared TOTAL above 64 would mean the record does not fit in the container at
all. A production unpacker validates the header before trusting it, and #1285
is the problem that computes whether a layout fits.
## Width
The total declared width is at most 60, so a packed value reaches
2^60 - 1 = 1152921504606846975. That needs a 64-bit integer: it is past the
2147483647 a signed 32-bit integer holds by nine orders of magnitude, and
past 2^53 = 9007199254740992, the largest integer a double represents
exactly, by a factor of 128.
So in JavaScript this needs BigInt twice over: >> and & would coerce a
Number to signed 32 bits, and even plain arithmetic on a Number would lose
the low digits of a 2^60 value. In Java the values must be read with
Long.parseLong, not through StreamTokenizer, whose nval is a double and
therefore cannot represent them either.
Constraints - `1 ≤ n ≤ 8` - `1 ≤ q ≤ 100000` - `1 ≤ each width`, and the widths sum to at most 60 - `0 ≤ each packed value < 2^(sum of widths)`
Input
The first line contains two integers n and q, separated by a space.
The second line contains n integers: the field widths, lowest field first.
Each of the next q lines contains one packed value.
Output
For each packed value print one line: its n field values, lowest field first, separated by single spaces.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.