Modulus operator

The modulus operator returns the remainder of an integer division. Sometimes written \(n \bmod m\) in mathematical expressions, the syntax in C++ is n % m. From the definition of remainder, \(n \bmod m\) is the integer \(r\) such that \(n = qm + r\) for \(q\) an integer, and \(|r| < |m|\).

Therefore, the result of \(n \bmod m\) must be between 0 and \(m-1\) when \(n\) and \(m\) are positive integers. For example, \(5 \bmod 3 = 2\); \(25 \bmod 3 = 1\), \(5 \bmod 7 = 5\), and \(5 \bmod 5 = 0\).

A common source of error is mixing up modulus and integer division operations.

int quotient = 7 / 3;

int remainder = 7 % 3;

The first operator, integer division, yields 2. The second operator yields 1. Thus, 7 divided by 3 is 2 with 1 left over.

This program shows the difference between the division operator and the modulus operator.

#include <iostream> using std::cout; int main () { int quotient = 7 / 3; int remainder = 7 % 3; cout << "quotient: " << quotient << '\n'; cout << "remainder: " << remainder << '\n'; return 0; }

The modulus operator turns out to be surprisingly useful. For example, you can check whether one number is divisible by another: if x % y is zero, then x is divisible by y.

Also, you can use the modulus operator to extract the rightmost digit or digits from a number. For example, x % 10 yields the rightmost digit of x (in base 10). Similarly x % 100 yields the last two digits.

sc-1-2: How could you detmine whether a variable x is odd?

• Use x % 2, and if the result is 0, it is odd.
• If you divide a number by two and it has no remainder, that means it is an even number!
• Use x % 2, and if the result is 1, it is odd.
• If you divide a number by two and it has a remainder of one, that means it is an odd number!
• Use x / 2, and if the result is 0, it is odd.
• Dividing a number by two won't give us the information we want.
• Use x / 2, and if the result is 1, it is odd.
• Dividing a number by two won't give us the information we want.

sc-1-3: Match the modulo expression to its result. Try again!
• 3 % 2
• 1
• 2 % 3
• 2
• 6 % 2
• 0
• 9 % 6
• 3

Construct a block of code that prints the remainder of 18 when divided by 13.

        int main () {
---
 int x = 18;
 int y = 13;
---
 cout << x % y;
---
 cout << y % x; #paired
---
 cout << x / y; #paired
---
 cout << y / x; #paired
---
}
        

Construct a function that prints whether a number is even.

        void is_even (int number) {
---
bool is_even (int number) { #distractor
---
 if (number % 2 == 0) {
---
  cout << true;
 }
---
 else {
---
  cout << false;
 }
---
}
        

There is more than one way to assign values to \(q\) and \(r\), depending on how integer division is interpreted. The most common mathematical definition computes the mod function as \(n \bmod m = n - m\lfloor n/m\rfloor\). In this case, \(-3 \bmod 5 = 2\). However, Java and C++ compilers typically use the underlying processor’s machine instruction for computing integer arithmetic. On many computers this is done by truncating the resulting fraction, meaning \(n \bmod m = n - m (\mathrm{trunc}(n/m))\). Under this definition, \(-3 \bmod 5 = -3\). Another language might do something different.

Unfortunately, for many applications this is not what the user wants or expects. For example, many hash systems will perform some computation on a record’s key value and then take the result modulo the hash table size. The expectation here would be that the result is a legal index into the hash table, not a negative number. Implementers of hash functions must either ensure that the result of the computation is always positive, or else add the hash table size to the result of the modulo function when that result is negative.

More to Explore

• From cppreference.com

  • Common math functions

  • remainder and remquo

  • fmod

  • div

Acknowledgements

This section is adapted from Problem Solving with Algorithms and Data Structures using C++, by Brad Miller and David Ranum, Luther College, and Jan Pearce, Berea College released under the CC BY-NC-SA 4.0, and Open Data Structures (OpenDSA) by Ville Karavirta and Cliff Shaffer which is distributed under the MIT License.

You have attempted of activities on this page