Có cách nào hiệu quả và di động để kiểm tra khi phép nhân với phép toán int64_t hoặc uint64_t tràn trong C không?phát hiện phép nhân uint64_t số nguyên tràn với C
Ví dụ, đối với việc bổ sung các uint64_t tôi có thể làm:
if (UINT64_MAX - a < b) overflow_detected();
else sum = a + b;
Nhưng tôi không thể có được một biểu thức đơn giản tương tự cho phép nhân.
Tất cả những gì xảy ra với tôi là phá vỡ các toán hạng thành các phần uint32_t cao và thấp và thực hiện phép nhân của những phần đó trong khi kiểm tra tràn, cái gì đó thực sự xấu xí và có thể không hiệu quả.
Cập nhật 1: Một số mã chuẩn thực hiện một số phương pháp tiếp cận thêm
Cập nhật 2: Jens Gustedt phương pháp bổ sung
chương trình chuẩn:
#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>
#define N 100000000
int d = 2;
#define POW_2_64 ((double)(1 << 31) * (double)(1 << 31) * 4)
#define calc_b (a + c)
// #define calc_b (a + d)
int main(int argc, char *argv[]) {
uint64_t a;
uint64_t c = 0;
int o = 0;
int opt;
if (argc != 2) exit(1);
opt = atoi(argv[1]);
switch (opt) {
case 1: /* faked check, just for timing */
for (a = 0; a < N; a++) {
uint64_t b = a + c;
if (c > a) o++;
c += b * a;
}
break;
case 2: /* using division */
for (a = 0; a < N; a++) {
uint64_t b = a + c;
if (b && (a > UINT64_MAX/b)) o++;
c += b * a;
}
break;
case 3: /* using floating point, unreliable */
for (a = 0; a < N; a++) {
uint64_t b = a + c;
if ((double)UINT64_MAX < (double)a * (double)b) o++;
c += b * a;
}
break;
case 4: /* using floating point and division for difficult cases */
for (a = 0; a < N; a++) {
uint64_t b = a + c;
double m = (double)a * (double)b;
if (((double)(~(uint64_t)(0xffffffff)) < m) &&
((POW_2_64 < m) ||
(b &&
(a > UINT64_MAX/b)))) o++;
c += b * a;
}
break;
case 5: /* Jens Gustedt method */
for (a = 0; a < N; a++) {
uint64_t b = a + c;
uint64_t a1, b1;
if (a > b) { a1 = a; b1 = b; }
else { a1 = b; b1 = a; }
if (b1 > 0xffffffff) o++;
else {
uint64_t a1l = (a1 & 0xffffffff) * b1;
uint64_t a1h = (a1 >> 32) * b1 + (a1l >> 32);
if (a1h >> 32) o++;
}
c += b1 * a1;
}
break;
default:
exit(2);
}
printf("c: %lu, o: %u\n", c, o);
}
Cho đến nay, trường hợp 4 sử dụng điểm nổi để lọc hầu hết các trường hợp là nhanh nhất khi nó được giả định rằng các luồng quá bất thường, ít nhất là trên máy tính của tôi, nơi nó chỉ là hai t imes chậm hơn so với trường hợp không có gì.
Trường hợp 5, là chậm hơn so với 4 30%, nhưng nó luôn luôn thực hiện như nhau, không có bất kỳ số trường hợp đặc biệt mà yêu cầu xử lý chậm như xảy ra với 4.
Làm thế nào về việc sử dụng dấu phẩy động và, nếu kết quả rất gần với 2^64, làm số nguyên nhân? Nếu kết quả dấu phẩy động trên 9.223370E + 18 thì sản phẩm chính xác chắc chắn sẽ lớn hơn 2^63, và nếu kết quả dấu phẩy động nhỏ hơn 9.223374E + 18 thì sản phẩm chính xác chắc chắn sẽ nhỏ hơn 3^63. Vì vậy, nếu kết quả dấu phẩy động là gần và số nguyên không dấu nhân năng suất lớn hơn 1ULL << 63, kết quả số nguyên sẽ không đại diện cho tràn. – supercat
@supercat: đó là trường hợp chủ yếu là trường hợp 4. – salva
Trường hợp bốn dường như sử dụng phân chia để kiểm tra xem kết quả có phù hợp hay không. Trên nhiều bộ vi xử lý, làm số nguyên không dấu nhân sẽ tự nó nhanh hơn nhiều (phân chia số nguyên thường là một trong các hướng dẫn chậm nhất). – supercat