Digit loops

Why this matters

Many small programs need to look at the digits of a number one at a time. A checkout page might check a card number with a rule that works digit by digit. A puzzle might ask whether a number reads the same backwards. A school program might add up the digits of a student ID. In each case the program must visit every digit, from one end of the number to the other.

Text can be split into characters easily, but a number is stored as a number, not as text. The C++ tools for this job are the remainder operator % and the integer division operator /. Together with a loop, they let you take a number apart digit by digit. This lesson builds that loop step by step and uses it for three jobs: summing the digits, reversing a number and checking for a palindrome.

The lesson uses the while loop from earlier in this module. The loop stops when the number has no digits left. Other loop ideas, such as loop invariants and half-open ranges, are covered in their own lessons in this module.

The idea: take off the last digit

Start with a plain question. What is the last digit of 4721? You can read it off the page: it is 1. A computer needs a rule for it, and the rule is the remainder operator.

The % operator gives the remainder after division. Dividing by 10 leaves a remainder equal to the last digit of a number written in base ten, which is the normal way people write numbers. So 4721 % 10 is 1.

The / operator, used on two whole numbers, does integer division. It throws away any remainder. So 4721 / 10 is 472. That is the number with its last digit removed.

Two words need a plain definition before we go on:

• A remainder is what is left over after a division. Seven divided by three is two with a remainder of one.
• Integer division is division that keeps only the whole-number part. The answer is rounded down toward zero, so 7 / 2 is 3 and not 3.5.

Put these two facts together and you have a loop. Take the last digit with %. Remove it with /. Repeat until nothing is left. The table below shows the steps for 4721.

When the number reaches 0, the loop stops. The four digits came out in the order 1, 2, 7, 4. They came out from the right end to the left end, which is backwards. This order matters for reversing a number later in the lesson.

Here is the shape of every digit loop in this lesson.

The output is:

digit 1
digit 2
digit 7
digit 4

Read the loop from the top. The test n > 0 asks whether any digits are left. Inside the loop, n % 10 gets the current last digit. The line n /= 10 is shorthand for n = n / 10. It removes that last digit, so the next pass sees the next digit. If you forget that line, n never changes, the test is always true, and the program never stops. The mistakes section shows what that looks like.

Example 1: sum the digits

The first job is to add up the digits of a number. For 4721 the answer is 4 + 7 + 2 + 1, which is 14. The loop above already visits each digit, so the sum needs only one extra variable that collects the digits as they come.

Put the loop in a function so it can be called with different numbers. A function is a named block of code that takes input and returns a result. The file below is complete and can be compiled as it is.

Compile it with g++ -std=c++20 -Wall -o digits digits.cpp and run ./digits. The output is:

14
0
9
0

The first line is the sum we worked out by hand. The second line is 0, which is correct: a number with no digits to add gives 0. The third line shows that a single digit works, because the loop runs once. The fourth line is wrong for most readers. The sum of the digits of -4721 should be 14, but the function returns 0. The reason is that the test n > 0 is false for any negative number, so the loop never runs. The mistakes section comes back to this.

Here is what happens inside sum_digits(4721), one pass at a time. total starts at 0. The first pass adds 1 and leaves n as 472. The second pass adds 2 and leaves n as 47. The third adds 7 and leaves 4. The fourth adds 4 and leaves 0. The test fails, the loop stops, and total holds 14. The variable total is called an accumulator, because it gathers a value a piece at a time.

Example 2: reverse a number

The second job is to reverse a number. The reverse of 4721 is 1274. Reversing needs the same digits as before, but this time they must be put together in the opposite order.

The trick is to build the answer as you go. Start with reversed equal to 0. For each digit taken off the right end of the number, multiply the answer so far by 10 to make room, then add the digit. A small trace makes this clear.

For 4721:

• Pass 1 takes digit 1. reversed is 0 times 10 plus 1, so it becomes 1.
• Pass 2 takes digit 2. reversed is 1 times 10 plus 2, so it becomes 12.
• Pass 3 takes digit 7. reversed is 12 times 10 plus 7, so it becomes 127.
• Pass 4 takes digit 4. reversed is 127 times 10 plus 4, so it becomes 1274.

The code follows the same pattern as the sum.

The output is:

1274
21
7
0

The second line deserves a closer look. The reverse of 1200 is 21, not 0021 and not 0012. A number does not store leading zeros, so the zeros at the end of the original number disappear when it is reversed. The first pass takes a 0 and adds it to 0, which leaves 0. The second pass also takes a 0 and leaves 0. Then the 2 and the 1 are added, and the answer is 21. This is correct for numbers in ordinary use, but it matters for the palindrome example below.

How big a number can this hold?

An int in C++ can hold values up to 2147483647 on the usual 32-bit int layout. Reversing a large number can produce a result that is too large for an int. Here is a program that tries it.

Without any extra checks, the program prints a wrong number. The reverse of 1000000009 is 9000000001, which is larger than an int can hold. Compiled with g++ -std=c++20 -Wall, the program prints 410065409 and exits with status 0. It gives no warning. The value wrapped around and the result is simply wrong.

The wrong value is not a random accident. In C++, signed integer overflow is undefined behaviour. That means the language does not promise what happens, so the compiler may do anything. Compiling with the undefined behaviour sanitizer, which is a checking mode of the compiler that stops at the first problem it finds, gives a clear message:

overflow.cpp:7:29: runtime error: signed integer overflow: 900000000 * 10 cannot be represented in type 'int'

The message names the file, the line, and the arithmetic that failed. To get it, compile with g++ -std=c++20 -Wall -fsanitize=undefined -g -o overflow_ub overflow.cpp. Use this flag while you learn, and do not leave it on in a program you ship, because it slows the program down. The fix for real code is to use a wider type such as long long, and to check the input size before you multiply. The palindrome example later in this lesson uses long long.

Example 3: check for a palindrome

A palindrome is a word or number that reads the same forwards and backwards. The number 12321 is a palindrome. The number 1230 is not, because its reverse is 0321, which is 321 when written as a number.

The simplest check uses the reverse function from example 2. Reverse the number, then compare the result with the original. If they are equal, the number is a palindrome.

The output is:

true
true
false
false
true
false

Each line checks one case. 12321 and 1221 read the same both ways, so they are true. 1230 reverses to 321, so it is false. The negative number -121 is false because the function returns false before it reverses anything. A minus sign at the front does not read the same from the other end, so the rule is that negative numbers are never palindromes in this definition. The number 7 is a palindrome because it has one digit. The number 1200 is false because its reverse is 21, and 21 is not 1200. This is the trailing-zero effect from example 2 at work.

The keyword bool is the type for true and false values. The line cout << boolalpha; makes the stream print the words true and false instead of 1 and 0. The boolalpha setting stays on for the rest of the program, which is why the later lines print words too.

A harder case: a digit-by-digit check

The reverse-and-compare method works, but it builds a second number, and that number can overflow. A different method compares the first digit with the last digit, the second with the second last, and so on, moving inward. This needs the place value of the leading digit, which it finds with a loop that multiplies a power of ten until n / place drops below 10.

The output is:

true
false
true
true

Here is how the first loop works. The variable place starts at 1. The loop multiplies place by 10 while n / place is still 10 or more. For 1230 the values are these: place is 1, then 10 (since 1230 / 1 is at least 10), then 100 (since 1230 / 10 is 123), then 1000 (since 1230 / 100 is 12). At 1000, the value 1230 / 1000 is 1, which is less than 10, so the loop stops. The final place is 1000, the place value of the leading digit.

The second loop compares the leading digit, found by n / place, with the last digit, found by n % 10. If they differ, the number is not a palindrome. If they match, the function removes both the leading digit and the last digit. The removal is n = (n % place) / 10, which keeps the middle digits, and place /= 100 moves the leading-digit position two places inward to match. The loop stops when fewer than two digits are left, and then the answer is true.

This method uses only numbers no larger than the original, so it does not overflow when the input fits in a long long. It is longer than the reverse-and-compare method, and for most tasks the simpler method is the better choice. Learn both, so you can explain why the second exists.

Common mistakes

Forgetting to change the number

The most common digit-loop bug is leaving out the line that removes the last digit. This program has the loop but never shortens n.

The compiler accepts it without a warning. When the program runs, n stays 4721 forever, so the loop never ends. Running it under a two-second time limit with timeout 2 ./bad_loop prints nothing and returns the status 124, which is the code that timeout uses when it stops a program. In a real program with no time limit, the program would run until someone stopped it. The fix is the line n /= 10; inside the loop.

Negative numbers

The loops in this lesson use n > 0 as their test. For a negative number that test is false from the start, so the loop does nothing. The sum of the digits of -4721 comes out as 0, which is wrong. The fix is to take the absolute value first, or to save the sign and work with the positive part. The practice exercises ask you to do this.

Overflow in the reverse

The reverse loop multiplies by 10 on every pass. A reversed number with ten digits can be too large for an int. The overflow program above printed 410065409 for an input whose reverse is 9000000001, and the sanitizer message names the exact line that overflowed. When you see a number that is too large to be right, suspect the arithmetic before you suspect the logic.

Dividing by the wrong power of ten

The % operator gives the last digit only when you divide by 10. Writing n % 100 gives the last two digits, and writing n / 100 removes two digits, not one. Each step in a digit loop must remove exactly one digit.

Practice

Exercise 1. Write count_digits, which returns the number of digits in a non-negative integer. The input 0 has one digit, so count_digits(0) should return 1, and count_digits(90210) should return 5.

Show the answer

The output is 1, 1 and 5. The loop is a do loop, which runs its body once before it tests the condition. This is what makes 0 count as one digit. A while loop would return 0 for the input 0.

Exercise 2. Write largest_digit, which returns the biggest digit in a number. It must work for negative numbers, so largest_digit(-805) should return 8.

Show the answer

The output is 7, 8 and 0. The function takes the absolute value first, which solves the negative-number problem from the mistakes section. The max function from the algorithm header keeps the larger of two values, so best only goes up.

Exercise 3. Write reverse_signed, which reverses the digits of a number and keeps its sign. reverse_signed(-120) should return -21, and reverse_signed(4721) should return 1274.

Show the answer

The output is -21, 1274 and -7. The sign is saved in its own variable and put back at the end. The ?: operator is the ternary operator, which picks one of two values depending on a test.

Exercise 4. Write all_digits_even, which returns true when every digit of a number is even. all_digits_even(2468) should be true, and all_digits_even(2461) should be false. Zero counts as even.

Show the answer

The output is true, false, true and true. The function returns false as soon as it finds an odd digit, so the loop can stop early. The do loop is needed for the input 0, which has one even digit.

Exercise 5. Write a function that prints each digit of a number on its own line, from left to right. For 4721 it should print 4, then 7, then 2, then 1. Hint: the digit loop produces the digits from right to left, so think about how to collect them first.

Show the answer

The output is 4, 7, 2 and 1, one per line. The loop collects the digits from right to left into a vector, which is a resizable list from the standard library. push_back adds an item to the end of the list. The second loop reads the list from its last item back to its first, which gives the digits in their written order.

Summary

• The % operator with 10 gives the last digit of a whole number, and / with 10 removes it.
• A digit loop runs while the number is greater than 0, and it must shorten the number on every pass.
• To sum digits, add each digit to an accumulator. To reverse a number, multiply the result by 10 and add the digit on each pass.
• A reversed number loses trailing zeros, and a large reversed value can overflow an int.
• A palindrome check can compare reversed and original numbers, or compare digits from both ends using a place value.
• Negative numbers need their sign handled separately, because the loop test n > 0 skips them.