Division: traps, defined results, remainders

Divide 7 by 0 in x86-64 assembly and the process dies with exit status 136; the same division on AArch64 returns 0 and the program carries on, and RISC-V returns all ones. Even −7 ÷ 2 can come back as −3, as −4 or as 9,223,372,036,854,775,804, depending on the language and on one instruction before the divide.

This lesson runs the divide instructions of x86-64, AArch64 and RISC-V on positive and negative operands, sets up the x86-64 dividend correctly and wrongly, provokes division by zero and INT64_MIN / -1 on each ISA, and takes apart the multiplication a compiler emits for x / 10.

Integer division rounds towards zero, and the remainder follows the dividend

Each version of sdivmod(a, b, &r) below returns a / b and stores the remainder at r, and udivmod does the same for unsigned operands. Compare how each ISA gets the remainder:

// sdivmod and udivmod for AArch64. AArch64 has no remainder instruction: r = a - (a / b) * b.
.text
.p2align 2
.globl _sdivmod
_sdivmod:                   // x0 = a, x1 = b, x2 = r
    sdiv x3, x0, x1         // x3 = a / b, rounded towards zero
    msub x4, x3, x1, x0     // x4 = x0 - x3 * x1, the remainder
    str x4, [x2]
    mov x0, x3
    ret
.globl _udivmod
_udivmod:
    udiv x3, x0, x1
    msub x4, x3, x1, x0
    str x4, [x2]
    mov x0, x3
    ret

# sdivmod and udivmod for x86-64, GNU as Intel syntax (Mach-O names carry a leading underscore).
# long sdivmod(long a, long b, long *r): returns a / b and stores a % b at *r.
# div and idiv divide the 128-bit number rdx:rax, so rdx must hold the high half of the dividend first.
.intel_syntax noprefix
.text
.globl _sdivmod
_sdivmod:
    mov rcx, rdx            # r arrives in rdx, which idiv overwrites: keep the pointer in rcx
    mov rax, rdi
    cqo                     # rdx = 64 copies of the sign bit of rax
    idiv rsi                # rax = quotient, rdx = remainder
    mov [rcx], rdx
    ret
.globl _udivmod
_udivmod:
    mov rcx, rdx
    mov rax, rdi
    xor edx, edx            # unsigned dividend: the high half is 0 (a 32-bit write clears all of rdx)
    div rsi
    mov [rcx], rdx
    ret

# sdivmod and udivmod for RV64 with the M extension (Linux ELF names have no underscore).
# The M chapter recommends div then rem on the same sources, quotient register not a source.
.text
.globl sdivmod
sdivmod:                    # a0 = a, a1 = b, a2 = r
    div a3, a0, a1          # a3 = a / b, rounded towards zero
    rem a4, a0, a1          # a4 = a % b, same sign as a
    sd a4, 0(a2)
    mv a0, a3
    ret
.globl udivmod
udivmod:
    divu a3, a0, a1
    remu a4, a0, a1
    sd a4, 0(a2)
    mv a0, a3
    ret

As in the multiplication lesson, the AArch64 build runs natively on Apple silicon under macOS, the x86-64 build runs through Rosetta 2, and the RISC-V file is assembled and read back. The driver divides ±7 by ±2, then the bits of −7 as an unsigned number:

// Calls the assembly sdivmod and udivmod on the same operands and prints quotient and remainder.
#include <inttypes.h>
#include <stdint.h>
#include <stdio.h>

int64_t sdivmod(int64_t a, int64_t b, int64_t *r);
uint64_t udivmod(uint64_t a, uint64_t b, uint64_t *r);

static void s(int64_t a, int64_t b) {
    int64_t r, q = sdivmod(a, b, &r);
    printf("signed    %3" PRId64 " / %2" PRId64 " = %2" PRId64 "  remainder %2" PRId64 "\n", a, b, q, r);
}

static void u(uint64_t a, uint64_t b) {
    uint64_t r, q = udivmod(a, b, &r);
    printf("unsigned  0x%016" PRIx64 " / %" PRIu64 " = %" PRIu64 "  remainder %" PRIu64 "\n", a, b, q, r);
}

int main(void) {
    s(7, 2);
    s(-7, 2);
    s(7, -2);
    s(-7, -2);
    u(7, 2);
    u((uint64_t)-7, 2);     // the bits of -7, divided as an unsigned number
    return 0;
}

import pathlib
import sys

sys.path.insert(0, str(pathlib.Path(__file__).parent / "sessions"))
import session

# One C driver, two assembly files: AArch64 runs natively, the x86-64 build runs through Rosetta 2.
session.run("""
clang -O1 -o divmod_a64 divmod.c aarch64/divmod.s
./divmod_a64 | tee a64.txt
clang -O1 -arch x86_64 -o divmod_x64 divmod.c x86_64/divmod.s
./divmod_x64 | diff a64.txt - && echo "x86-64 printed the same 6 lines"
""")

# macOS cannot run RISC-V: assemble the M-extension file and read it back.
session.run("""
llvm-mc --triple=riscv64 -mattr=+m -filetype=obj -o divmod_rv.o riscv/divmod.s
llvm-objdump -d --no-show-raw-insn divmod_rv.o
""")

$ clang -O1 -o divmod_a64 divmod.c aarch64/divmod.s
$ ./divmod_a64 | tee a64.txt
signed      7 /  2 =  3  remainder  1
signed     -7 /  2 = -3  remainder -1
signed      7 / -2 = -3  remainder  1
signed     -7 / -2 =  3  remainder -1
unsigned  0x0000000000000007 / 2 = 3  remainder 1
unsigned  0xfffffffffffffff9 / 2 = 9223372036854775804  remainder 1
$ clang -O1 -arch x86_64 -o divmod_x64 divmod.c x86_64/divmod.s
$ ./divmod_x64 | diff a64.txt - && echo "x86-64 printed the same 6 lines"
x86-64 printed the same 6 lines
$ llvm-mc --triple=riscv64 -mattr=+m -filetype=obj -o divmod_rv.o riscv/divmod.s
$ llvm-objdump -d --no-show-raw-insn divmod_rv.o

divmod_rv.o:	file format elf64-littleriscv

Disassembly of section .text:

0000000000000000 <sdivmod>:
       0:      	div	a3, a0, a1
       4:      	rem	a4, a0, a1
       8:      	sd	a4, 0x0(a2)
       c:      	mv	a0, a3
      10:      	ret

0000000000000014 <udivmod>:
      14:      	divu	a3, a0, a1
      18:      	remu	a4, a0, a1
      1c:      	sd	a4, 0x0(a2)
      20:      	mv	a0, a3
      24:      	ret

−7 / 2 gave −3, not −4: every signed divide here is a truncating divisiontruncating division: Integer division that rounds the quotient towards zero, as C and the signed divide instructions of x86-64, AArch64 and RISC-V do: -7 / 2 is -3, and the remainder takes the sign of the dividend., which drops the fraction of −3.5 and so rounds towards zero. The remainder then has to make (a / b) × b + a % b = a hold, which gives it the sign of the dividend: −7 % 2 is −1, and 7 % −2 is 1. C requires exactly this, “the algebraic quotient with any fractional part discarded”, in 6.5.6 of its standard, so compiled C and these instructions agree.

The last line shows that division, unlike addition, cares about signedness. The bits 0xfffffffffffffff9 are −7 as a signed number and 18,446,744,073,709,551,609 as an unsigned one, and udivmod divided the second: 9,223,372,036,854,775,804 remainder 1. So each ISA has a signed and an unsigned divide:

AArch64 has no remainder instruction. msub x4, x3, x1, x0 computes x0 − x3 × x1, the dividend minus the quotient times the divisor, which is the remainder by definition. RISC-V has rem and remu, and its M chapter recommends the div then rem pair on the same sources, with a quotient register that is neither source, so that a core can fuse the two into one division. RV64 adds divw, divuw, remw and remuw, which divide the low 32 bits and sign-extend the 32-bit result.

x86-64 divides rdx:rax, so the high half must be set first

idiv rsi does not divide rax by rsi. It divides the 128-bit number in the register pair rdx:rax, writes the quotient to rax and the remainder to rdx; the 32-bit idiv esi divides edx:eax the same way. So before every divide, rdx must hold the upper half of the dividend: copies of the sign bit for a signed division, which cqo writes (cdq for edx:eax), or 0 for an unsigned one, which xor edx, edx writes because a 32-bit write clears the whole register. That is also why sdivmod above copies its pointer argument out of rdx first: the divide would overwrite it. Step through −7 / 2, then the same division with the wrong set-up:

Both mistakes pass a quick test. The two functions below get the set-up wrong on purpose: div_junk never clears rdx, so the divide uses whatever its third argument left there, and idiv_zeroed uses the unsigned set-up before a signed divide:

# Two x86-64 divisions with the dividend's high half set up wrongly, GNU as Intel syntax.
.intel_syntax noprefix
.text
.globl _div_junk
_div_junk:                  # unsigned long div_junk(unsigned long a, unsigned long b, unsigned long junk)
    mov rax, rdi            # the low half of the dividend
    div rsi                 # BUG: no xor edx, edx, so rdx still holds junk, the third argument
    ret
.globl _idiv_zeroed
_idiv_zeroed:               # long idiv_zeroed(long a, long b)
    mov rax, rdi
    xor edx, edx            # BUG: the unsigned set-up before a signed divide; cqo was meant
    idiv rsi
    ret

import pathlib
import sys

sys.path.insert(0, str(pathlib.Path(__file__).parent / "sessions"))
import session

# The same two bugs, on inputs that hide them and on inputs that show them (x86-64, through Rosetta 2).
session.run("""
clang -O1 -arch x86_64 -o setup_x64 setup.c x86_64/setup.s
./setup_x64 junk 7 2 0; echo "exit=$?"
./setup_x64 junk 7 2 1; echo "exit=$?"
{ ./setup_x64 junk 7 1 1; } 2>/dev/null; s=$?; echo "exit=$s signal=$(kill -l $s)"
./setup_x64 zeroed 7 2; echo "exit=$?"
./setup_x64 zeroed -7 2; echo "exit=$?"
""")

$ clang -O1 -arch x86_64 -o setup_x64 setup.c x86_64/setup.s
$ ./setup_x64 junk 7 2 0; echo "exit=$?"
rdx = 0: 7 / 2 gave 3
exit=0
$ ./setup_x64 junk 7 2 1; echo "exit=$?"
rdx = 1: 7 / 2 gave 9223372036854775811
exit=0
$ { ./setup_x64 junk 7 1 1; } 2>/dev/null; s=$?; echo "exit=$s signal=$(kill -l $s)"
exit=136 signal=FPE
$ ./setup_x64 zeroed 7 2; echo "exit=$?"
7 / 2 gave 3
exit=0
$ ./setup_x64 zeroed -7 2; echo "exit=$?"
-7 / 2 gave 9223372036854775804
exit=0

With rdx = 0, div_junk printed the right 3. With rdx = 1 the dividend was 2⁶⁴ + 7, and the divide returned 9,223,372,036,854,775,811 without complaint, because that quotient still fits in 64 bits. With the divisor 1, the quotient 2⁶⁴ + 7 does not fit, and the process died with status 136. idiv_zeroed is right for 7 / 2 and wrong for −7 / 2, which it divided as 2⁶⁴ − 7. The Intel manual lists both outcomes under DIV and IDIV: the result goes to rax and rdx, and a quotient too large for rax raises the divide error, #DE, exactly as a zero divisor does.

Division by zero traps on x86-64 and returns a value elsewhere

The two operations that have no correct 64-bit answer are a division by zero and INT64_MIN / -1, whose true quotient, +2⁶³, is one more than the largest signed 64-bit number. This session runs both on each ISA that can run here, each case in its own process so that a crash cannot hide the next one:

// edge a b: divides a by b with the assembly sdivmod and prints the quotient and the remainder.
// Each case runs as its own process, so a case that traps cannot hide the others.
#include <inttypes.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>

int64_t sdivmod(int64_t a, int64_t b, int64_t *r);

int main(int argc, char **argv) {
    if (argc != 3) return 2;
    int64_t a = strtoll(argv[1], NULL, 0), b = strtoll(argv[2], NULL, 0), r;
    int64_t q = sdivmod(a, b, &r);
    printf("%" PRId64 " / %" PRId64 " = %" PRId64 "  remainder %" PRId64 "\n", a, b, q, r);
    return 0;
}

import pathlib
import sys

sys.path.insert(0, str(pathlib.Path(__file__).parent / "sessions"))
import session

# Division by zero and INT64_MIN / -1, each in its own process. A process killed by a signal ends with status
# 128 + the signal's number; kill -l turns that status back into the signal's name. The braces send the shell's
# own crash message (which names the process number) to /dev/null.
session.run("""
clang -O1 -o edge_a64 edge.c aarch64/divmod.s
./edge_a64 7 0; echo "exit=$?"
./edge_a64 -9223372036854775808 -1; echo "exit=$?"
clang -O1 -arch x86_64 -o edge_x64 edge.c x86_64/divmod.s
./edge_x64 7 2; echo "exit=$?"
{ ./edge_x64 7 0; } 2>/dev/null; s=$?; echo "exit=$s signal=$(kill -l $s)"
{ ./edge_x64 -9223372036854775808 -1; } 2>/dev/null; s=$?; echo "exit=$s signal=$(kill -l $s)"
""")

$ clang -O1 -o edge_a64 edge.c aarch64/divmod.s
$ ./edge_a64 7 0; echo "exit=$?"
7 / 0 = 0  remainder 7
exit=0
$ ./edge_a64 -9223372036854775808 -1; echo "exit=$?"
-9223372036854775808 / -1 = -9223372036854775808  remainder 0
exit=0
$ clang -O1 -arch x86_64 -o edge_x64 edge.c x86_64/divmod.s
$ ./edge_x64 7 2; echo "exit=$?"
7 / 2 = 3  remainder 1
exit=0
$ { ./edge_x64 7 0; } 2>/dev/null; s=$?; echo "exit=$s signal=$(kill -l $s)"
exit=136 signal=FPE
$ { ./edge_x64 -9223372036854775808 -1; } 2>/dev/null; s=$?; echo "exit=$s signal=$(kill -l $s)"
exit=136 signal=FPE

AArch64 never traps on a divide. sdiv by zero returned 0, so msub computed the remainder as 7 − 0 × 0 = 7, and INT64_MIN / -1 returned INT64_MIN with remainder 0: the true quotient wrapped. On x86-64 both cases raised #DE, and macOS ended the process with a signalsignal: A notification the operating system delivers to a process, such as SIGFPE after an integer divide fault; unhandled, it ends the process, and the shell reports status 128 plus the signal number.. Status 136 is 128 + 8, the shell’s way of reporting a process killed by signal 8, and kill -l names it: FPE, the signal that signal(7) lists as 8 on every architecture and describes as an erroneous arithmetic operation. On Linux too, an instruction that raises a math fault gets its thread a SIGFPE, and sigaction(2) lists FPE_INTDIV, integer divide by zero, among the reasons the signal can carry.

RISC-V code does not run on Apple silicon, so its column comes from the table in its M chapter, not from a run:

RISC-V’s unsigned divu by zero also returns all ones, the largest unsigned number. Its manual explains why it chose values over a trap: a trap “would be the only arithmetic trap in the standard ISA”, and a language that wants one can add a single, almost never taken branch after the divide. x86-64’s idiv traps on INT64_MIN % -1 as well, although its true remainder, 0, fits: one instruction computes both, and the quotient overflowed.

C does not choose between the ISAs. Its standard makes division by zero undefined behaviourundefined behaviour: What the C standard calls an operation for which it sets no requirements at all, such as dividing by zero; a compiler may assume a correct program never performs one., and when a / b is not representable, both a / b and a % b are undefined too, which covers INT64_MIN % -1. A compiler may assume neither case happens, so the ISA’s behaviour only shows through in assembly, and robust code tests b == 0 and a == INT64_MIN && b == -1 before it divides. In tests, clang’s -fsanitize=integer-divide-by-zero and -fsanitize=signed-integer-overflow, which covers INT_MIN / -1, report both cases where they happen.

Compilers divide by a constant with a multiply and a shift

A compiler that knows the divisor in advance does not have to divide at all. This file divides an int by 10 and takes its remainder, and the session compiles it with -O2, the usual optimisation level, on each ISA, then with -Oz, the level that clang’s documentation says reduces code size further than -Os. Apple’s clang has no RISC-V backend, so the RISC-V lines use the clang of Homebrew’s LLVM:

// Division and remainder by the constant 10, for 32-bit int.
int div10(int x) { return x / 10; }
int mod10(int x) { return x % 10; }

import pathlib
import sys

sys.path.insert(0, str(pathlib.Path(__file__).parent / "sessions"))
import session

# x / 10 and x % 10 compiled for speed (-O2) on each ISA, then div10 alone compiled for size (-Oz).
session.run("""
clang -O2 -fomit-frame-pointer -arch x86_64 -c -o speed_x64.o div10.c
objdump -d --no-show-raw-insn -M intel speed_x64.o
clang -O2 -c -o speed_a64.o div10.c
otool -tV speed_a64.o | cat
/opt/homebrew/opt/llvm/bin/clang --target=riscv64-linux-gnu -march=rv64gc -O2 -c -o speed_rv.o div10.c
llvm-objdump -d --no-show-raw-insn speed_rv.o
""")

session.run("""
clang -Oz -fomit-frame-pointer -arch x86_64 -c -o size_x64.o div10.c
objdump -d -M intel --disassemble-symbols=_div10 size_x64.o
clang -Oz -c -o size_a64.o div10.c
otool -tV size_a64.o | cat
/opt/homebrew/opt/llvm/bin/clang --target=riscv64-linux-gnu -march=rv64gc -Oz -c -o size_rv.o div10.c
llvm-objdump -d --disassemble-symbols=div10 size_rv.o
""")

$ clang -O2 -fomit-frame-pointer -arch x86_64 -c -o speed_x64.o div10.c
$ objdump -d --no-show-raw-insn -M intel speed_x64.o

speed_x64.o:	file format mach-o 64-bit x86-64

Disassembly of section __TEXT,__text:

0000000000000000 <_div10>:
       0:      	movsxd	rax, edi
       3:      	imul	rax, rax, 0x66666667
       a:      	mov	rcx, rax
       d:      	shr	rcx, 0x3f
      11:      	sar	rax, 0x22
      15:      	add	eax, ecx
      17:      	ret
      18:      	nop	dword ptr [rax + rax]

0000000000000020 <_mod10>:
      20:      	movsxd	rax, edi
      23:      	imul	rcx, rax, 0x66666667
      2a:      	mov	rdx, rcx
      2d:      	shr	rdx, 0x3f
      31:      	sar	rcx, 0x22
      35:      	add	ecx, edx
      37:      	add	ecx, ecx
      39:      	lea	ecx, [rcx + 4*rcx]
      3c:      	sub	eax, ecx
      3e:      	ret
$ clang -O2 -c -o speed_a64.o div10.c
$ otool -tV speed_a64.o | cat
speed_a64.o:
(__TEXT,__text) section
_div10:
0000000000000000	mov	w8, #0x6667
0000000000000004	movk	w8, #0x6666, lsl #16
0000000000000008	smull	x8, w0, w8
000000000000000c	asr	x8, x8, #34
0000000000000010	add	w0, w8, w8, lsr #31
0000000000000014	ret
_mod10:
0000000000000018	mov	w8, #0x6667
000000000000001c	movk	w8, #0x6666, lsl #16
0000000000000020	smull	x8, w0, w8
0000000000000024	asr	x8, x8, #34
0000000000000028	add	w8, w8, w8, lsr #31
000000000000002c	mov	w9, #0xa
0000000000000030	msub	w0, w8, w9, w0
0000000000000034	ret
$ /opt/homebrew/opt/llvm/bin/clang --target=riscv64-linux-gnu -march=rv64gc -O2 -c -o speed_rv.o div10.c
$ llvm-objdump -d --no-show-raw-insn speed_rv.o

speed_rv.o:	file format elf64-littleriscv

Disassembly of section .text:

0000000000000000 <div10>:
       0:      	lui	a1, 0x66666
       4:      	addi	a1, a1, 0x667
       8:      	mul	a0, a0, a1
       c:      	srli	a1, a0, 0x3f
      10:      	srai	a0, a0, 0x22
      12:      	add	a0, a0, a1
      14:      	ret

0000000000000016 <mod10>:
      16:      	lui	a1, 0x66666
      1a:      	addi	a1, a1, 0x667
      1e:      	mul	a1, a0, a1
      22:      	srli	a2, a1, 0x3f
      26:      	srai	a1, a1, 0x22
      28:      	add	a1, a1, a2
      2a:      	slli	a2, a1, 0x1
      2e:      	slli	a1, a1, 0x3
      30:      	add	a1, a1, a2
      32:      	subw	a0, a0, a1
      34:      	ret
$ clang -Oz -fomit-frame-pointer -arch x86_64 -c -o size_x64.o div10.c
$ objdump -d -M intel --disassemble-symbols=_div10 size_x64.o

size_x64.o:	file format mach-o 64-bit x86-64

Disassembly of section __TEXT,__text:

0000000000000000 <_div10>:
       0: 89 f8                        	mov	eax, edi
       2: 6a 0a                        	push	0xa
       4: 59                           	pop	rcx
       5: 99                           	cdq
       6: f7 f9                        	idiv	ecx
       8: c3                           	ret
$ clang -Oz -c -o size_a64.o div10.c
$ otool -tV size_a64.o | cat
size_a64.o:
(__TEXT,__text) section
_div10:
0000000000000000	mov	w8, #0xa
0000000000000004	sdiv	w0, w0, w8
0000000000000008	ret
_mod10:
000000000000000c	mov	w8, #0xa
0000000000000010	sdiv	w9, w0, w8
0000000000000014	msub	w0, w9, w8, w0
0000000000000018	ret
$ /opt/homebrew/opt/llvm/bin/clang --target=riscv64-linux-gnu -march=rv64gc -Oz -c -o size_rv.o div10.c
$ llvm-objdump -d --disassemble-symbols=div10 size_rv.o

size_rv.o:	file format elf64-littleriscv

Disassembly of section .text:

0000000000000000 <div10>:
       0: 45a9         	li	a1, 0xa
       2: 02b5453b     	divw	a0, a0, a1
       6: 8082         	ret

At -O2 no ISA divided. x86-64 multiplied the sign-extended x by 0x66666667 with imul, shifted the 64-bit product right by 34 (0x22), and added the product’s sign bit. AArch64 built the same constant with mov and movk, used smull, a 32 × 32 → 64-bit signed multiply, then asr #34 and an add of the sign bit; RISC-V built it with lui and addi and did the same with mul, srai and srli. mod10 computed the quotient that way, multiplied it back by 10 (x86-64 with add and lea, RISC-V with two shifts and an add, AArch64 with msub) and subtracted. At -Oz all three kept the divide: cdq and idiv ecx in a 9-byte function on x86-64, sdiv on AArch64, divw on RISC-V. The choice shows how the compiler ranks the two: five or six instructions are worth spending to avoid one divide, except when the smallest code is the goal.

The constant is 2³⁴ ÷ 10 rounded up. Multiplying by it scales x / 10 up by 2³⁴, the shift scales it back with rounding down, and the add of the sign bit turns rounding down into rounding towards zero for negative results. Step through both signs:

Why 34 and not 32? This program builds the constant for each shift from 32 up, tests it against Python’s own division on the hardest inputs (both ends of the int range and around 0) and on 200,000 seeded random ones, and stops at the first shift that passes:

"""Where 0x66666667 comes from: the constant clang uses for a 32-bit int divided by 10.

The compiled code computes q = (x * M) >> S (an arithmetic shift, which rounds down) and then adds 1 when q is
negative, which turns rounding down into rounding towards zero, as C's / requires. M is 2**S / D rounded up.
For each shift S this program builds M, tests it against Python's own division on the hardest inputs and on
200,000 seeded random ones, and stops at the first S that passes.
"""

import random

D = 10                       # the divisor; change it and run again
LOW, HIGH = -2**31, 2**31 - 1


def truncating_div(x, d):
    """C's x / d for int: the quotient rounded towards zero."""
    q = abs(x) // abs(d)
    return q if (x < 0) == (d < 0) else -q


def compiled(x, m, s):
    """What the instructions compute: multiply, shift right with rounding down, add 1 if negative."""
    q = (x * m) >> s
    return q + 1 if q < 0 else q


rng = random.Random(10)
tests = [x for x in range(LOW, LOW + 2**16)] + [x for x in range(-2**16, 2**16)]
tests += [x for x in range(HIGH - 2**16, HIGH + 1)] + [rng.randint(LOW, HIGH) for _ in range(200_000)]

for s in range(32, 40):
    m = -(-(2**s) // D)      # 2**s / D rounded up
    bad = next((x for x in tests if compiled(x, m, s) != truncating_div(x, D)), None)
    if bad is None:
        print(f"S = {s}: M = {m} = {m:#x}, every test agrees ({len(tests)} inputs)")
        excess = m * D - 2**s
        print(f"M * D - 2**S = {excess}, so the largest error is {excess} * 2**31 / ({D} * 2**{s})"
              f" = {excess * 2**31 / (D * 2**s):.4g}, below 1/{D} = {1 / D:.4g}")
        break
    print(f"S = {s}: M = {m:#x} fails first at x = {bad}: {compiled(bad, m, s)} instead of {truncating_div(bad, D)}")

S = 32: M = 0x1999999a fails first at x = -2147483639: -214748364 instead of -214748363
S = 33: M = 0x33333334 fails first at x = -2147483639: -214748364 instead of -214748363
S = 34: M = 1717986919 = 0x66666667, every test agrees (462145 inputs)
M * D - 2**S = 6, so the largest error is 6 * 2**31 / (10 * 2**34) = 0.075, below 1/10 = 0.1

Rounding the constant up adds a small error to every estimate, and the error grows with x. With shifts of 32 and 33 it reaches 0.2 for an x near 2³¹, too much: −2,147,483,639 ÷ 10 is −214,748,363.9, and 0.2 more pushes the estimate past −214,748,364. At 34, M × 10 − 2³⁴ = 6, so the error is at most 6 × 2³¹ ÷ (10 × 2³⁴) = 0.075 for any 32-bit x. The fractional part of x / 10 is at most 0.9, and 0.9 + 0.075 never reaches the next whole number, so the rounding always lands on the true quotient. This multiplication by a reciprocalmultiplication by a reciprocal: Division by a constant d done as a multiplication by 2^S / d rounded up, a right shift by S and a fix for negative results; with the right S it is exact for every input of its width. is exact, not an approximation.

Practise

Use an Apple silicon Mac for these, or the Linux setup from setting up the toolchain; on Linux, write each function name without its leading underscore:

1. Write safe_divmod(a, b, &q, &r) for AArch64 and for x86-64 that returns 1 and leaves q and r alone for b == 0 and for INT64_MIN / -1, and otherwise stores both and returns 0. Change edge.c to call it, and run the four cases of the edge session on both builds: they must print the same lines and never end with status 136.
2. Set D = 1000 in magic.py and run it. Then compile int div1000(int x) { return x / 1000; } with -O2 for AArch64, and find the multiplier and the shift that magic.py printed in the listing.
3. Set D = 7 and run magic.py again. Its multiplier is larger than 2³¹, so it does not fit a signed 32-bit operand: compile x / 7 for AArch64 and find the extra instruction clang adds to make up for it.

Interview questions

A warm-up for freshers: what are −7 / 2 and −7 % 2 in C on x86-64, AArch64 and RISC-V, and why do all three agree?

−7 / 2 is −3 and −7 % 2 is −1 on all three. C defines integer division as the algebraic quotient with the fraction discarded, so −3.5 becomes −3, rounded towards zero, and requires (a / b) * b + a % b == a, which makes the remainder −1, with the sign of the dividend. The signed divide instructions of the three ISAs, idiv, sdiv and div, all round towards zero as well, so a compiler can use them directly. The answer changes in languages that round down instead: Python’s -7 // 2 is −4 and -7 % 2 is 1, which is the usual surprise when code moves between them.

For interview practice beyond the warm-up, the bank has a question on designing a portable checked division and another on a crash that appears on one ISA only, both with a first step and follow-ups:

Key takeaways

• Signed division on x86-64, AArch64 and RISC-V rounds towards zero, as C requires, and the remainder takes the sign of the dividend; unlike addition, division needs separate signed and unsigned instructions.
• x86-64 div and idiv divide rdx:rax and write the quotient to rax and the remainder to rdx, so cqo must come before idiv and xor edx, edx before div; the wrong set-up returns a huge quotient or traps.
• AArch64 has no remainder instruction and computes it with msub, while RISC-V has rem and remu, best placed right after the matching divide.
• Division by zero and INT64_MIN / -1 raise #DE on x86-64, which ends the process with SIGFPE and status 136, while AArch64 and RISC-V return defined values, and C leaves both cases undefined.
• A compiler optimising for speed replaces x / 10 with a multiplication by 0x66666667, a shift by 34 and a sign fix, which is exact for every 32-bit x; at -Oz it keeps the divide.