Past exam of the year 1 of the computer science course of the University of Oxford / 2023 / Digital systems, linear algebra and introduction to formal proof / 1 / c / Solution

For a 32-bit machine word and $1\le k\le 31$, use a left bit shift followed by a logical right shift:The left shift discards all but the lowest $k$ bits and moves those retained bits to the top. The logical right shift returns them to their original positions and fills the rest with zero. Hence r1 contains $a\mathrm{mod}{2}^k$, the remainder identified in (b). For $k=0$ the remainder is zero; for $k=32$ it is $a$, so these endpoints can be handled directly.

On a reduced instruction set computer, a bit mask such as $2^k-1$ may not fit an instruction's immediate field. Masking may therefore require materializing the constant in another processor register, possibly using several instructions or a memory load. Small shift counts are directly encodable, so the two shifts can save code space, a temporary processor register, or a load. This is an architecture-dependent advantage, rather than a universal speed claim. The source's compact instruction forms support these immediate shifts, while their bitwise AND form takes its other operand from a processor register.^[ref]