Abstract

a % n gives the remainder when a is divided by n. It’s used for wrap-around (circular buffers, clock arithmetic), hashing into buckets, parity checks, and keeping large numbers small in modular arithmetic. Two things catch people out: negative numbers, where languages disagree on the sign of the result, and performance, where % 2ᵏ can be replaced by & (2ᵏ − 1), but only for non-negative values.

Cue

• What does -7 % 3 give in Java or C, and in Python? → -1 in Java/C (truncated), 2 in Python (floored)
• How do you get a non-negative result in Java? → Math.floorMod(a, n)
• When does x % n == x & (n - 1) hold? → When n is a power of two and x ≥ 0
• Is num % 2 == 1 a safe odd check? → No. It’s -1 for negative odd numbers, so use num % 2 != 0 or (num & 1) == 1

Definition

For integers $a$ and $n\ne 0$, division gives a quotient $q$ and a remainder $r$ with:

$$a=q\cdot n+r$$

The languages disagree on how to round $q$, which decides the sign of $r$:

Convention	$q$ rounds	Sign of $r$ follows	-7 % 3	Languages
Truncated	toward 0	the dividend $a$	-1	Java %, C/C++, Rust, JavaScript, Go
Floored	toward −∞	the divisor $n$	2	Python %, Ruby, Java Math.floorMod

Mathematicians mean the floored (or Euclidean) version when they say “mod”: the result is always in $[0,n)$ for positive $n$.

-7 % 3                 // -1
Math.floorMod(-7, 3)   //  2
((-7 % 3) + 3) % 3     //  2, the classic manual fix

Parity: num % 2 vs num & 1

num & 1 keeps only the lowest bit: 1 for odd numbers, 0 for even. That works for negative numbers too, because in two’s complement every odd number has its lowest bit set.

boolean isOdd(int num) { return (num & 1) == 1; }   // correct for negatives
boolean isOdd(int num) { return num % 2 != 0; }     // also correct
boolean isOdd(int num) { return num % 2 == 1; }     // BUG: -3 % 2 == -1

Is & 1 faster? Only without optimisation, and not by much. Division instructions are slow, but compilers already replace % 2 (and any % 2ᵏ) with shifts and masks:

• For an unsigned value, x % 2 compiles to a single and, the same as x & 1.
• For a signed value, x % 2 needs a few extra instructions to give negative numbers the truncated sign. x % 2 != 0 doesn’t, because the sign no longer matters, so the compiler emits a single and.

Choose the one that reads most clearly. Reach for the mask when you’ve measured a difference or when the bit is what you actually mean.

Compiler Explorer (x86-64 gcc 14.2, no optimisation)

return num & 1; compiles to an and eax, 1, with no division:

This screenshot shows num % 1, not num % 2

Any integer % 1 is 0, so gcc folds the whole function to mov eax, 0. It doesn’t show the cost of % 2. To compare properly, compile return num % 2; next to return num & 1;, at -O0 and at -O2, for both int and unsigned.

Powers of two: x % 2ᵏ == x & (2ᵏ − 1)

$2^k-1$ in binary is $k$ ones, so masking with it keeps the low $k$ bits, which is the remainder:

int bucket = hash & (capacity - 1);   // capacity must be a power of two

This is why java.util.HashMap keeps its table size a power of two. For negative x the mask gives the floored result (-7 & 3 == 1) while % gives the truncated one (-7 % 4 == -3). That makes the mask useful for array indexes, which must not be negative.

Modular arithmetic

Remainders survive addition, subtraction and multiplication, so you can reduce at each step and never overflow:

$$(a+b)\mathrm{mod}m=((a\mathrm{mod}m)+(b\mathrm{mod}m))\mathrm{mod}m$$ $$(a\cdot b)\mathrm{mod}m=((a\mathrm{mod}m)\cdot (b\mathrm{mod}m))\mathrm{mod}m$$

That’s why coding challenges ask for answers “mod $10^9+7$“. It’s a prime, and $(10^9+7{)}^2$ fits in a 64-bit long, so one multiplication of two reduced values can’t overflow.

static final int MOD = 1_000_000_007;
long result = (a % MOD) * (b % MOD) % MOD;   // with a, b as long

Division doesn’t work this way. Dividing modulo a prime $p$ means multiplying by the modular inverse, $b^{p-2}\mathrm{mod}p$ by Fermat’s little theorem, or using the extended Euclidean algorithm from Algos, Number Theory, GCD.

Related

• Algos, Number Theory, GCD: Euclid’s algorithm is repeated modulo
• Algos, Efficiency

---