Sometimes you need to calculate the sum of digits of an integer.
A straightforward approach is:
int sumDigits(int num) {
int result = 0;
while (num > 0) {
result += num % 10;
num /= 10;
}
return result;
}
This implementation performs both a modulo (%) and an integer division (/) on every iteration.
Reformulating the Problem
For simplicity, assume:
0 <= num <= 9999
Represent the number as:
num = a + 10b + 100c + 1000d
where a, b, c, and d are decimal digits.
The desired result is:
sum = a + b + c + d
Notice that:
num
= a + 10b + 100c + 1000d
= (a + b + c + d)
+ (9b + 99c + 999d)
Therefore:
num - sum
= 9b + 99c + 999d
= 9(b + 11c + 111d)
Expanding further:
num - sum
= 9(b + c + 10c + d + 10d + 100d)
= 9((100d + 10c + b) + (10d + c) + d)
Now observe that integer division naturally produces these terms:
num / 10 = b + 10c + 100d
num / 100 = c + 10d
num / 1000 = d
Adding them together gives:
num / 10 + num / 100 + num / 1000
= (100d + 10c + b)
+ (10d + c)
+ d
Hence:
num - sum
= 9 * (num / 10 + num / 100 + num / 1000)
and finally:
sum
= num - 9 * (num / 10 + num / 100 + num / 1000)
which translates directly into code:
int sumDigits(int num) {
return num
- 9 * (num / 10
+ num / 100
+ num / 1000);
}
Finally
Compared to the conventional loop, this approach:
- Eliminates modulo operations entirely.
The same idea generalizes to larger fixed-width numbers:
sumDigits(num) =
num - 9 * Σ(num / 10^k), k = 1 .. n - 1
Whether this is actually faster depends on the target CPU, compiler, and the number of digits involved, but it is an interesting algebraic transformation of the classic digit-sum algorithm.