= Signed power-of-two division by biasing
{title2=$\operatorname{trunc}(a/2^k)=\left\lfloor(a+(2^k-1)\mathbf1_{a<0})/2^k\right\rfloor$}
For signed <two's complement> <integers>, a conditional positive bias converts the rounding behaviour of an <arithmetic right shift> into <C integer division>. It can be formed without a conditional branch by turning the sign <bit> into either zero or a low-$k$-<bit> <bit mask>.
\b[Proof.] Nonnegative $a$ needs no adjustment. If $a<0$, write $-a=2^kq+r$, $0\leq r<2^k$. Then $a+(2^k-1)=-2^kq+(2^k-1-r)$, whose quotient rounded down is $-q$, exactly the quotient truncated towards zero. The bias fits safely for $1\leq k<n$ in an $n$-<bit> signed word: it is added only to negative inputs, and the largest possible adjusted input is $2^k-2$. The corresponding remainder is $((a+b)\bmod2^k)-b$, where $b=(2^k-1)\mathbf1_{a<0}$.
Back to article page
