= Solution
Extract low bits and fill the <integer> positions from right to left:
``
var remaining = int_part
var pos = digits - 1
while (pos >= 0) {
res(pos) = if ((remaining & 1) == 0) '0' else '1'
remaining = remaining >>> 1
pos -= 1
}
``
At the start of an iteration, the <loop invariant> says that positions $pos+1,\ldots,digits-1$ contain the correct low bits and
$$
int\_part=remaining\,2^{digits-1-pos}
+\sum_{t=pos+1}^{digits-1}(res(t)-\mathtt{'0'})2^{digits-1-t}.
$$
The bitwise AND extracts the remainder modulo two; the shift supplies its quotient. These two facts preserve the <loop invariant>. The <loop variant> is $pos+1$. The width established in part (c) ensures that `remaining` is zero at exit, so \b[the first `digits` entries encode the whole <integer> part]. For zero the single entry becomes `'0'`. There are no explicit multiplications or divisions, and no extra digit <array> is needed.
Back to article page
