Floor division and modulo for negatives

Why this matters

Division and remainder look simple until a number goes below zero. A program that sorts temperatures into buckets of 10 degrees puts -3 into the wrong bucket. A program that steps back through a list of five names can ask for position -1 and crash. A program that wraps an hour on a 24-hour clock can show a negative hour. The C++ operators / and % round toward zero, which matches school arithmetic for positive numbers but gives surprising answers for negative ones. This lesson shows what the operators actually do, why the results differ, and how to write two small helper functions that behave the way you expect.

Evaluation order, which decides which part of a long expression runs first, is the subject of the next lesson in this module. This lesson only covers division and remainder.

Two ways to round a negative number

Start with a plain question. What is 7 divided by 2? The answer is 3.5. If you want a whole number, you must drop the fraction. This is called rounding, and there is more than one way to do it when the answer is negative.

• Truncation cuts off the fraction. The result moves toward zero. -3.5 becomes -3.
• Floor moves down to the next whole number on the number line. -3.5 becomes -4.

Picture a number line with zero in the middle. The point -3.5 sits between -4 and -3. Truncation picks -3, which is closer to zero. Floor picks -4, which is further to the left and so lower. "Negative infinity" is just the far-left end of the number line, so "round toward negative infinity" means "round down". For positive numbers the two methods agree. 3.5 becomes 3 either way.

C++ uses truncation for integer division. The / operator on two int values drops the fraction and moves toward zero. Since C++11 the standard requires this behaviour, so every compiler does the same thing. The program below prints a small table so you can see the result for each sign combination.

The output on the machine that checked this lesson is:

a   b   a/b   a%b
7   2   3     1
-7   2   -3     -1
7   -2   -3     1
-7   -2   3     -1

Read the second row. -7 divided by 2 is -3.5. Truncation drops the .5 and moves toward zero, so the answer is -3. Floor would give -4. Read the fourth row. -7 divided by -2 is 3.5, which truncates to 3. A negative divided by a negative is positive, so the answer is positive.

The / operator is not wrong. It does what the standard says. The problem is only that many tasks want floor, not truncation.

The remainder follows the left side

The remainder operator % returns what is left over after the division. For positive numbers you may know it from clock arithmetic. 9 % 4 is 1, because 4 goes into 9 two times and 1 is left over.

The two operators are linked by one rule. For any two integers a and b, where b is not zero, this always holds:

a = (a / b) * b + (a % b)

Check the first row of the table. 7 = 3 * 2 + 1, which is correct. Check the second row. -7 = (-3) * 2 + (-1), which is also correct. So the remainder of -7 divided by 2 must be -1, not 1. The rule forces it.

In C++ the remainder takes the sign of its left operand, the number before the % sign. This is called the sign of the dividend. The right operand only sets the size of each step. The fourth row shows the same idea with two negatives. -7 % -2 is -1 because the left operand is negative.

A negative remainder is a problem when you use % to wrap a position into a range. Suppose you have 5 items numbered 0 to 4, and you want the position one step before 0. The correct answer is 4. But -1 % 5 gives -1, and -1 is not a valid position.

Writing floor_div

We want a function that returns the floor of a divided by b. Here is the plan. First use / and % to get the truncated answer and the remainder. Then, if the remainder is not zero and the true answer is negative, subtract 1. Truncation moved the answer up toward zero, so one step down puts it back on the floor.

The helper below is a function template. The template line lets the same code work for int, long, and long long. The word signed_integral is a concept, a rule that accepts only signed whole-number types. It refuses unsigned types, which never hold negative numbers and do not need this fix. The mistakes section shows the error you get when you break this rule.

The output on the machine that checked this lesson is:

a   b   floor_div   floor_mod
7   2   3           1
-7   2   -4           1
7   -2   -4           -1
-7   -2   3           -1
-6   3   -2           0

Walk through the row for -7 and 2 by hand.

1. q = a / b gives -3, the truncated answer.
2. r = a % b gives -1, the remainder. Its sign follows a, which is negative.
3. signs_differ is true. The remainder is negative (r < 0 is true) and the divisor is not (b < 0 is false). The two checks disagree, so the expression (r < 0) != (b < 0) is true.
4. r != 0 is also true, so --q runs. q becomes -4.

Now the row for -6 and 3. q = -2 and r = 0. The division is exact, so there is no fraction to drop and no reason to adjust. The r != 0 check stops the adjustment, and the answer stays -2. Without that check, the helper would wrongly return -3.

The signs_differ check works because the remainder always has the sign of a. If the remainder and the divisor have different signs, then a and b have different signs too. That means the true answer is negative, and truncation has moved it up toward zero, so one step down is needed. When a and b are both positive or both negative, the answer is already on the correct side.

Writing floor_mod

floor_mod returns the remainder that matches the sign of the divisor. For a positive divisor, the result is always between 0 and b - 1. That is the range you need for wrapping a position into a list.

The steps are the same as before. Start with the C++ remainder. If it is not zero and its sign differs from b, add b once. Here are three cases worked out by hand:

• floor_mod(-7, 2): the C++ remainder is -1. It is negative and b is positive, so add 2. The result is 1.
• floor_mod(-1, 5): the C++ remainder is -1. Add 5. The result is 4.
• floor_mod(7, -2): the C++ remainder is 1. It is positive and b is negative, so add -2. The result is -1.

For every nonzero b, the two helpers satisfy a = floor_div(a, b) * b + floor_mod(a, b). You can check the last case in your head. floor_div(7, -2) is -4, and -4 * -2 is 8. Then 8 + (-1) is 7, which is the original number.

Worked example 1: temperature buckets

A weather program sorts readings into buckets that are 10 degrees wide. Bucket 0 holds readings from 0 to 9. Bucket 1 holds 10 to 19. Bucket -1 should hold -10 to -1, and bucket -2 should hold -20 to -11.

Now try the plain / operator on -3. -3 / 10 is 0, because the fraction .3 is dropped toward zero. So -3 would land in bucket 0 along with 0 to 9, which is wrong. floor_div fixes this. The program below uses the same two helpers as before, with the same code, plus a second example that wraps a position in a list.

The output on the machine that checked this lesson is:

temperature -25 is in bucket -3
temperature -10 is in bucket -1
temperature -3 is in bucket -1
temperature 0 is in bucket 0
temperature 9 is in bucket 0
temperature 10 is in bucket 1
hour -1 on a 24-hour clock: 23
one step back from position 0: eve
plain % would give index -1

Check the bucket results against the rule. -10 is in bucket -1, because -10 / 10 is exactly -1 and the remainder is 0, so there is no adjustment. -11 is in bucket -2, because the answer is -1.1, and the floor is -2. The output for -25 is bucket -3, since -2.5 floors to -3.

The list example uses static_cast<int>(names.size()). The function size() returns an unsigned number, and mixing unsigned and signed values in arithmetic can give surprising results, so the program converts the size to int first. The list has 5 names, so position -1 wraps to position 4, which is "eve".

Worked example 2: the same idea with long long

The helpers work for any signed whole-number type. A long long holds numbers up to about 9 * 10 to the power 18, and the helpers use the same steps. The LL suffix on a number makes it a long long literal, the way f makes a float literal.

The program below also compares the helper with std::floor from <cmath>. It uses two divisions, one with ints and one with doubles, to show a common mistake.

The output on the machine that checked this lesson is:

long long: -4
std::floor with int division: -3
std::floor with double division: -4

The second line is the surprise. std::floor works on the result of -7 / 2, and that division has already happened with ints. It truncated to -3 before floor ran, so floor had nothing left to fix. The third line divides by 2.0, which makes the division happen in doubles, so the result is -3.5 and floor brings it to -4.

When you need floor division for values that fit in a double, the static_cast<double> form works. For large values, a double cannot store every whole number exactly. A double has about 15 to 16 significant decimal digits. The helper in this lesson uses only integer operations, so it does not have this problem.

Common mistakes

Mistake 1: calling floor on an integer division

The output in the worked example shows the error. The line floor(-7 / 2) prints -3. The fix is either the helper, or divide as doubles: floor(-7 / 2.0) prints -4, and floor(static_cast<double>(a) / b) does the same for variables.

Mistake 2: using % to wrap a negative position

Here is a program that wraps a position with % and then reads a list.

#include <iostream>
#include <vector>
using namespace std;
 
int main() {
    vector<int> v{1, 2, 3, 4, 5};
    int idx = -1 % 5;
    cout << "idx = " << idx << endl;
    cout << v.at(idx) << endl;
    return 0;
}

The output on the machine that checked this lesson is:

idx = -1
terminate called after throwing an instance of 'std::out_of_range'
  what():  vector::_M_range_check: __n (which is 18446744073709551615) >= this->size() (which is 5)

The idx = -1 line is printed first. Then at rejects the index. The message shows the index became a huge number, 18446744073709551615. That happens because at takes an unsigned size, and -1 turned into the largest unsigned value. The program then stops with an abort, which is why the message starts with "terminate called". The fix is floor_mod(-1, 5), which returns 4.

Mistake 3: dividing by zero

Dividing an integer by zero has no answer, and C++ does not define one. A compiler warns when the zero is written directly in the code:

m2.cpp: In function ‘int main()’:
m2.cpp:3:15: warning: division by zero [-Wdiv-by-zero]
    3 |     int x = 5 / 0;
      |             ~~^~~

When the zero is only known at run time, the compiler cannot warn, and the program stops. The next program prints a line, then divides by a variable holding zero.

#include <iostream>
using namespace std;
 
int main() {
    int a = -7;
    int zero = 0;
    cout << "about to divide" << endl;
    cout << a / zero << endl;
    return 0;
}

The output on the machine that checked this lesson is:

about to divide

The program stopped after the first line, and the shell reported exit code 136. The endl in the first line flushes the output (sends the text out now instead of holding it in a buffer), which is why the first line appeared. Without a flush, the line can be lost when the program stops this way. The fix is to check the divisor before the division.

Mistake 4: the smallest int divided by -1

The smallest int is -2147483648. Dividing it by -1 would give 2147483648, which does not fit in an int. In C++ that is undefined behaviour, so the program can do anything. The helpers in this lesson do not guard against it. If your values can reach that case, use a wider type such as long long, or check for it before dividing.

Mistake 5: passing an unsigned type to the helper

If you pass unsigned values to floor_div, the compiler stops with an error. The next program is short so the error is easy to read.

#include <concepts>
template <std::signed_integral T>
constexpr T floor_div(T a, T b) { return a / b; }
 
int main() {
    unsigned x = floor_div(7u, 2u);
    return static_cast<int>(x);
}

The first lines of the output on the machine that checked this lesson are:

m5.cpp: In function ‘int main()’:
m5.cpp:6:27: error: no matching function for call to ‘floor_div(unsigned int, unsigned int)’
    6 |     unsigned x = floor_div(7u, 2u);
      |                  ~~~~~~~~~^~~~~~~~
m5.cpp:6:27: note: there is 1 candidate
m5.cpp:3:13: note: candidate 1: ‘template<class T>  requires  signed_integral<T> constexpr T floor_div(T, T)’
    3 | constexpr T floor_div(T a, T b) { return a / b; }
      |             ^~~~~~~~~
m5.cpp:3:13: note: template argument deduction/substitution failed:
m5.cpp:3:13: note: constraints not satisfied

The key line is "constraints not satisfied". It means the type did not meet the signed_integral rule. Unsigned values never go below zero, so truncation and floor agree for them. Use / and % directly for unsigned values.

Practice

Try each exercise on paper first, then run your answer to check it.

Exercise 1. What does -9 / 4 print, and what does -9 % 4 print?

Show the answer

-9 / 4 prints -2, because -2.25 truncates toward zero. -9 % 4 prints -1, because -9 = (-2) * 4 + (-1).

Exercise 2. What do floor_div(-9, 4) and floor_mod(-9, 4) return?

Show the answer

They return -3 and 3. The truncated quotient is -2 with remainder -1. The remainder is nonzero and negative while 4 is positive, so the quotient becomes -3 and the remainder becomes -1 + 4 = 3.

Exercise 3. Write a function int day_index(int offset) that returns a number from 0 to 6 for any offset, positive or negative. Use floor_mod. Then say what day_index(-8) returns.

Show the answer

int day_index(int offset) {
    return floor_mod(offset, 7);
}

day_index(-8) returns 6. The C++ remainder of -8 and 7 is -1, which is negative while 7 is positive, so 7 is added and the result is 6.

Exercise 4. A student writes floor(a / 2) with int a = -7 and expects -4. What does it print, and why?

Show the answer

It prints -3. The division a / 2 runs first with ints, truncates to -3, and then floor receives -3, which it returns unchanged. The fix is floor(a / 2.0), which prints -4, or floor_div(a, 2).

Exercise 5. What do floor_div(10, -3) and floor_mod(10, -3) return? Check your answer with the rule a = floor_div(a, b) * b + floor_mod(a, b).

Show the answer

They return -4 and -2. The truncated quotient is -3 with remainder 1. The remainder is positive while -3 is negative, so the quotient becomes -4 and the remainder becomes 1 + (-3) = -2. The rule gives (-4) * (-3) + (-2) = 12 - 2 = 10, which is the original number.

Exercise 6. A list has 6 items numbered 0 to 5. You are standing at position 1 and want the position 3 steps back. Which position is it, and which helper gives it?

Show the answer

It is position 4, and floor_mod(1 - 3, 6) gives it. The expression 1 - 3 is -2. The C++ remainder of -2 and 6 is -2, which is negative while 6 is positive, so 6 is added and the result is 4.

Summary

• C++ / on integers truncates toward zero, so -7 / 2 is -3, not -4.
• C++ % takes the sign of its left operand, so -7 % 2 is -1.
• For any nonzero b, a = (a / b) * b + (a % b) always holds.
• floor_div subtracts 1 from the truncated quotient when the remainder is nonzero and its sign differs from b.
• floor_mod adds b to the remainder under the same condition, which gives a position from 0 to b - 1 for a positive b.
• std::floor cannot fix an integer division that has already truncated, so divide as doubles or use a helper.