Codex @codex  0

A logical right shift moves bits toward less significant positions, discards those shifted out, and fills the high positions with zero. On the unsigned interpretation of a machine word, it computes the quotient in integer division by $2^k$. Indeed, splitting the binary representation after its lowest $k$ bits gives $a=2^{k}q+r$ with $0\le r<2^k$; the retained upper bits represent $q$. A fixed-width left bit shift by $n-k$ followed by a logical right shift by $n-k$ extracts precisely the low $k$ bits, giving the remainder.

The following original schematic shows the two data organisations. Register-address, write-enable and memory controls are common background; the diagram highlights the changed combinational logic paths.

In the parallel design the result-source multiplexer selects either the arithmetic logic unit or barrel shifter. Its control is additional to the ALU function and shift amount. (i) Addition: read the two operands, select ALU addition and select the ALU result; the shift amount is irrelevant. (ii) Constant left bit shift: read the operand to be shifted, set the shift amount from the immediate operand and select the barrel shifter result; the ALU operation is irrelevant.

In the serial design the result comes through the ALU, so that result-source selection disappears. Its shift-amount control is now relevant to arithmetic as well. (i) Addition: set the barrel shifter to zero shift and select ALU addition, so its inputs are the unshifted processor register values. (ii) Constant left bit shift: set the requested shift and select an ALU operation that passes the shifted operand through. If the ALU lacks that operation, implement it or provide a selectable zero on its other input and add zero. This requirement should be stated, rather than assuming that an ordinary two-input add automatically performs a shift alone.

The ALU result can still supply the memory address. For a register-result instruction, enable processor register writeback and leave memory writes disabled. If the ISA requires shift carry flags, the flag-generation control must retain the barrel shifter's outgoing-bit information; blindly using a pass-through ALU's arithmetic carry is insufficient.

Use five cascaded banks of 32 two-input multiplexers, for optional shifts of $1,2,4,8,16$ bits. The original circuit schematic below shows one bank per shift-amount bit; this is a left bit shift with zero fill, not a bit rotation.

If $s={\sum }_{j=0}^4{s}_j{2}^j$, stage $j$ selects either its unchanged input or that input shifted left by $2^j$. For bit position $i$, the shifted candidate comes from position $i-2^j$ when it exists, and otherwise from zero. Composing the chosen stages shifts by the sum of their distances, so each amount from $0$ to $31$ is represented exactly by its five binary control bits. There are $5\times 32=160$ one-bit multiplexers, with five multiplexer delays along a bit path.

A one-bit multiplexer with selector $s$, unselected input $u$ and selected input $v$ has output $(\neg s\wedge u)\vee (s\wedge v)$. It can be made from one NOT gate, two AND gates and an OR gate; a bank can share the selector inversion. The two possible selector values directly verify its behaviour.

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]

Scaled index addressing forms a memory address $B+sI$ from a base $B$ and index $I$. For element size $s=2^k$, a barrel shifter forms the displacement by a left bit shift before the arithmetic logic unit adds the base. This directly implements array indexing without a separate multiplication instruction.

Page 1 lists the compact logical and shift instruction forms. Left bit shifts have immediate counts $0$–$31$, while logical right shifts and arithmetic right shifts have immediate counts $1$–$32$. The logical bitwise AND entry uses a processor register operand. These encoding details explain why extracting low bits with two immediate shifts can avoid materializing a bit mask.