Digital Systems 3 min read

Multiply, divide and modulus

Multiplying in binary is shifting and adding. Shifting left multiplies by 2, shifting right divides by 2, and the remainder of a division by a power of two is just the low bits. General division is the expensive one.

Left, divide by 4: x is 13, 1101. Shifting right by two gives 11, which is 3, the quotient. Masking with 3 keeps the low two bits, 01, which is 1, the remainder. Right, multiply 5 by 3: 101 plus 101 shifted left by one, 1010, gives 1111, which is 15. — Dividing 13 by 4: a shift gives the quotient, a mask gives the remainder.

Multiplying is shift and add

Each 1 bit in the multiplier adds a shifted copy of the multiplicand. For 5 × 3, the multiplier 011 has two 1s: 101 (5) plus 101 shifted left once, 1010 (10), is 1111, which is 15. Hardware multipliers do this in parallel; the idea is the same.

Powers of two are free

Shifting left by one doubles a value, since every bit moves up one place: 0011 (3) becomes 0110 (6), and two shifts make 1100 (12). Shifting right halves it, dropping the lowest bit. Compilers turn a multiply or divide by a constant power of two into a shift for you, but writing the shift makes the intent clear in register code.

Division and modulus

Dividing by 4 is a shift right by 2, and the remainder is the two bits that were shifted out. With x = 13 (1101): x >> 2 is 11 (3) and x & 3 is 01 (1), so 13 = 4 × 3 + 1. In general, for a power of two N, x % N equals x & (N - 1), which is how a ring buffer wraps its index without a division.

uint8_t x = 13;
uint8_t q = x >> 2;    // 3
uint8_t r = x & 3;     // 1, same as x % 4

These tricks hold for unsigned values. Right-shifting a negative signed value is implementation-defined in C, so use unsigned types for bit work.

Division by anything else

Dividing by a value that is not a power of two needs a divider. Cortex-M3 and above have a hardware divide instruction; Cortex-M0 and M0+ do not, so a division is a call into a software routine that takes many more cycles. Check your core's reference manual, and in a fast loop prefer a shift, a mask or a precomputed reciprocal.