Вот прием для определения, переполняется ли умножение двух целых чисел без знака.
Мы отмечаем, что если мы умножим двоичное число шириной N бит на двоичное число шириной M бита, произведение не будет содержать более N + M битов.
Например, если нас попросят умножить трехбитное число на двадцать девять разрядных чисел, мы знаем, что это не переполняет тридцать два бита.
#include <stdlib.h>
#include <stdio.h>
int might_be_mul_oflow(unsigned long a, unsigned long b)
{
if (!a || !b)
return 0;
a = a | (a >> 1) | (a >> 2) | (a >> 4) | (a >> 8) | (a >> 16) | (a >> 32);
b = b | (b >> 1) | (b >> 2) | (b >> 4) | (b >> 8) | (b >> 16) | (b >> 32);
for (;;) {
unsigned long na = a << 1;
if (na <= a)
break;
a = na;
}
return (a & b) ? 1 : 0;
}
int main(int argc, char **argv)
{
unsigned long a, b;
char *endptr;
if (argc < 3) {
printf("supply two unsigned long integers in C form\n");
return EXIT_FAILURE;
}
a = strtoul(argv[1], &endptr, 0);
if (*endptr != 0) {
printf("%s is garbage\n", argv[1]);
return EXIT_FAILURE;
}
b = strtoul(argv[2], &endptr, 0);
if (*endptr != 0) {
printf("%s is garbage\n", argv[2]);
return EXIT_FAILURE;
}
if (might_be_mul_oflow(a, b))
printf("might be multiplication overflow\n");
{
unsigned long c = a * b;
printf("%lu * %lu = %lu\n", a, b, c);
if (a != 0 && c / a != b)
printf("confirmed multiplication overflow\n");
}
return 0;
}
Несколько тестов: (в 64-битной системе):
$ ./uflow 0x3 0x3FFFFFFFFFFFFFFF
3 * 4611686018427387903 = 13835058055282163709
$ ./uflow 0x7 0x3FFFFFFFFFFFFFFF
might be multiplication overflow
7 * 4611686018427387903 = 13835058055282163705
confirmed multiplication overflow
$ ./uflow 0x4 0x3FFFFFFFFFFFFFFF
might be multiplication overflow
4 * 4611686018427387903 = 18446744073709551612
$ ./uflow 0x5 0x3FFFFFFFFFFFFFFF
might be multiplication overflow
5 * 4611686018427387903 = 4611686018427387899
confirmed multiplication overflow
Шаги в might_be_mul_oflow почти наверняка медленнее, чем простое деление теста, по крайней мере, на основных процессорах, используемых на настольных рабочих станциях, серверах и мобильных устройствах. На чипах без хорошей поддержки деления это может быть полезно.
Мне приходит в голову, что есть еще один способ сделать это раннее испытание на отклонение.
Мы начинаем с пары чисел arng и brng, которые инициализируются в 0x7FFF...FFFF и 1.
Если a <= arng и b <= brng, можно сделать вывод, что переполнения нет.
В противном случае мы смещаем arng вправо и смещаем brng влево, добавляя один бит к brng, так что они равны 0x3FFF...FFFF и 3.
Если arng равно нулю, закончите; в противном случае повторите в 2.
Функция теперь выглядит так:
int might_be_mul_oflow(unsigned long a, unsigned long b)
{
if (!a || !b)
return 0;
{
unsigned long arng = ULONG_MAX >> 1;
unsigned long brng = 1;
while (arng != 0) {
if (a <= arng && b <= brng)
return 0;
arng >>= 1;
brng <<= 1;
brng |= 1;
}
return 1;
}
}