Integer division

Division of integers that returns an integer quotient rather than an exact fraction. A rounding convention is required for negative operands. For $n\ge 0$ and $d>0$, the quotient is $q=\lfloor n/d\rfloor$ and the remainder is $r=n-qd$ with $0\le r<d$.

For an $n$-bit unsigned dividend $a$ and positive divisor $b$, read the dividend bits from most to least significant. If the processed prefix is $p$, maintain $p=bQ+R$ with $0\le R<b$. Appending bit $d$ gives trial remainder $T=2R+d$; append quotient bit $[T\ge b]$ and replace the remainder by $T-b[T\ge b]$. This preserves the quotient–remainder identity.

The old dividend and new quotient can share one $n$-bit processor register: after $k$ iterations its value is $(a{2}^k\mathrm{mod}{2}^n)+Q_k$, where $Q_k<2^k$. The shifted dividend occupies the upper positions and the accumulated quotient occupies the lower positions, so no information is overwritten. The high processor register holds $R_k$. For an $n$-bit dividend the next trial remainder is no larger than the next prefix, hence fits in $n$ bits through the final iteration. This last bound is specific to the dividend width; it must not be assumed for unrestricted multiword dividends.

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.

Proof. Nonnegative $a$ needs no adjustment. If $a<0$, write $-a=2^{k}q+r$, $0\le r<2^k$. Then $a+(2^k-1)=-2^{k}q+(2^k-1-r)$, whose quotient rounded down is $-q$, exactly the quotient truncated towards zero. The bias fits safely for $1\le 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)\mathrm{mod}{2}^k)-b$, where $b=(2^k-1)1_{a<0}$.

For representable integer quotients with nonzero divisor, C integer division discards the fractional part towards zero and defines the remainder by $a=bq+r$. Thus a nonzero remainder has the dividend's sign. For example, $-13=5(-2)+(-3)$, so division by five returns quotient $-2$ and remainder $-3$. This convention differs from division rounded down, which would return quotient $-3$ and nonnegative remainder $2$. Division by zero and an unrepresentable quotient are excluded.^[ref]