= Solution
\b[Use four working <processor registers> by packing the growing <quotient> into the vacated low <bits> of the shifting dividend.] The following is A32 <assembly language> with conditional execution, an allowed instance of the question's general 32-bit <Reduced instruction set computer>. It is not restricted to the sixteen-bit encodings in the supplied <Thumb instruction set> table. On entry `r0` is the dividend and `r1` the positive divisor; `r2` becomes the high <remainder> <machine word> and `r3` counts iterations. The <quotient> is returned in `r0` and the ordinary <remainder> remains in `r2`.
``
mov r2, #0
mov r3, #32
loop:
adds r0, r0, r0
adcs r2, r2, r2
cmp r2, r1
subcs r2, r2, r1
adc r0, r0, #0
subs r3, r3, #1
bne loop
bx lr
``
Here `subcs` means conditional `sub` when <arithmetic carry> is set, \b[without] the flag-setting suffix. `adc` also preserves flags. Consequently the <arithmetic carry> from `cmp` survives until it is inserted as the next <quotient> <bit>. The loop has seven instructions, one of them conditional, and no data-dependent branch. Its sole branch is the backwards loop branch, taken 31 times. It uses no separate <quotient> <processor register>, zero <processor register>, temporary comparison <processor register> or saved <arithmetic carry> <processor register>. A <Thumb instruction set> rendering using conditional execution would need an explicit conditional-execution encoding such as `it cs`; that is an additional encoded instruction, not an unexplained free operation.
The <packed restoring division> <loop invariant> relates it to the displayed algorithm. Specifically, let $M=2^{32}$, let $a$ retain its original mathematical value, and let $k$ be the number of completed iterations. Define the processed prefix $p_k=\lfloor a/2^{32-k}\rfloor$, its <quotient> $Q_k=\lfloor p_k/b\rfloor$ and <remainder> $R_k=p_k-bQ_k$. The <processor register> <loop invariant> is
$$
\text{high}=R_k,\qquad \text{low}=(a2^k\bmod M)+Q_k,\qquad 0\le Q_k<2^k.
$$
The two terms in the low <machine word> occupy disjoint <bit> positions. Its next outgoing <arithmetic carry> is therefore the next \i[original dividend <bit>], not a <quotient> <bit>. `adds` shifts the low <machine word>; `adcs` doubles the high <remainder> and incorporates that dividend <bit>. `cmp` decides whether this trial <remainder> is at least the divisor; `subcs` performs the conditional subtraction, and `adc` appends its decision to the shifted <quotient>. This is exactly the doubling, compare/subtract and quotient-bit update, with the counter maintained separately. Before processing <bit> $k\le32$, the trial <remainder> is at most $p_k<2^k\le M$, so the high-word addition does not require a hidden 33rd <remainder> <bit> for this 32-bit dividend problem. After 32 iterations the residual dividend portion is zero, giving the stated outputs.
There is a \b[printed source error] in the auxiliary bound. At the initial state, choosing valid inputs $a=b=1$ makes the printed strict inequality $r2^j<b2^{32}$ false. The algorithm instead preserves $0\le r<b2^{32}$ for its \i[unpacked 64-bit] variable, together with its printed equality <loop invariant>. Doubling and subtracting $b2^{32}$ when necessary preserves that corrected bound. At termination the equality becomes $a2^{32}=qb2^{32}+r$; since $r$ is then divisible by $2^{32}$, it gives $0\le a-qb<b$. This source error does not invalidate the algorithm or the packed implementation. The figure is mathematical pseudocode: its `2^32` denotes exponentiation, rather than C's XOR operator.
The displayed A32 routine assembled successfully with Clang and was disassembled to check the conditional and non-flag-setting forms. Its <carry flag> model was checked exhaustively at an eight-bit <machine word> size and against boundary and randomized 32-bit divisions. No native <ARM architecture family> execution is claimed.
Back to article page
