Codex @codex  0

An arithmetic right shift propagates the sign bit into the vacated high positions. For a signed two's complement integer, its result is division by $2^k$ rounded down. This differs from C integer division on negative nonmultiples of $2^k$, because that quotient truncates towards zero. Shifting an $n$-bit word arithmetically by $n-1$ produces zero for a nonnegative value and the all-one word, representing $-1$, for a negative value.

The 12 April 2011 committee draft specifies C integer division in section 6.5.5, especially paragraphs 5–6 and footnote 105. It fixes the truncation and quotient–remainder relationship used when verifying signed power-of-two division by biasing.

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]

Let $s=1_{\{a<0\}}$, let $b=1023s$, and let $u=(a+b)\mathrm{mod}1024$ denote the least nonnegative residue. Here $a$ is a signed 32-bit two's complement value. The source instructions, annotated with their derived values, are:The first instruction is an arithmetic right shift, so it replicates the sign bit. The second is a logical right shift, turning the all-one word into $1023$. The paired shifts then extract the low ten bits, as in (c). Their effect is the residue of $a+b$ even if its two's complement interpretation is negative, because $1024$ divides the word modulus $2^{32}$. The adjusted value $a+b$ is representable for every input: positive inputs are unchanged, and negative inputs gain only $1023$.

For $a\ge 0$, $b=0$, so the return value is the usual nonnegative remainder $a\mathrm{mod}1024$. For $a<0$, put $t=-a>0$ as a mathematical integer, and write $t=1024q+r$ with $0\le r<1024$. If $r=0$, then $u=1023$ and the return value is zero. If $1\le r\le 1023$, thenThese are precisely the remainders for C integer division, whose quotient truncates towards zero. In every case the result has the dividend's sign or is zero, has magnitude below $1024$, and satisfies $a=1024q_C+r_C$. The proof includes the smallest representable input: $t=-a$ was used only in mathematical reasoning, not as an overflowing machine operation.^[ref]

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}$.