Làm thế nào để xác định trước khi bàn tay nếu một tính toán unsigned có thể có thể tràn?

Question

Là một dự án cá nhân, tôi đang làm việc để triển khai loại số chính xác tùy ý cho dự án thú cưng của tôi.

Tôi đã biết về tất cả các thư viện phổ biến, được thử nghiệm và mạnh mẽ ở đó thực hiện việc này. Tôi muốn làm việc trên một giải pháp như một dự án giáo dục tự cải thiện.

Tôi đang nghiên cứu khu vực và cố gắng tìm hiểu xem có cách nào để khoảng dự đoán liệu một thao tác có gây ra tràn trước khi tôi thực sự thực hiện các phép tính hay không. Tôi cũng không quan tâm đến những mặt tích cực sai.

Tôi muốn có thể sử dụng không gian nhỏ nhất phù hợp để tính toán. Nếu tính toán sẽ nằm trong giới hạn bản địa của nó, tôi giữ nó ở đó.

Ví dụ: Multiplying two 64 bit Integers if each are large enough will cause an overflow. Tôi muốn phát hiện điều này và chỉ chuyển đổi số thành loại số của mình nếu kết quả có thể vượt quá 64 bit độ phân giải. Tôi sẽ làm việc với đã ký số trong thử nghiệm này.

Cách hiệu quả nhất, hiệu quả nhất để phát hiện tràn/tràn là gì?

Answer 1

Chỉ lấy bit cao nhất trong cả hai số, dịch chuyển sang trái, nếu kết quả (ví dụ: nhân) của các số đó gây ra tràn, bạn có khả năng cơ hội tốt để bị tràn.

Mặc dù nó không chính xác, nhưng nó rất nhanh và chỉ báo tốt rằng bạn cần loại dữ liệu lớn hơn cho kết quả.

này chỉ có thể có ý nghĩa cho các kiểu dữ liệu lớn mà các nhà điều hành rất tốn kém, vì những điều đơn giản (ngay cả đối với số 64bit), tôi nghĩ bạn có thể dựa vào số học dựng sẵn của CPU .. xem câu hỏi này: Undefined behavior when exceed 64 bits

Answer 2

Có paper của John Regehr về điều đó.

Answer 3

Nó hầu như luôn luôn dễ dàng hơn (và thường nhanh hơn) để thực hiện tính toán ngây thơ, và phát hiện nếu tràn xảy ra. Có lý do cụ thể nào khiến bạn muốn phát hiện khả năng trước khi thực hiện tính toán không?

Thường thì khá dễ phát hiện nếu xảy ra tràn khi tính toán kết thúc. Bởi vì các hoạt động ngây thơ có giá rẻ, điều này cũng không thêm nhiều vào chi phí tính toán của bạn nếu xảy ra tràn, ngay cả khi bạn cần phải làm lại một số công việc. (Thông thường, tuy nhiên, bạn thậm chí sẽ không cần phải làm điều đó). Đây là một ví dụ đơn giản (rất): nếu tôi thêm hai số 64 bit chưa ký, tôi có thể kiểm tra tràn bằng cách so sánh số tiền với một trong các phần bổ sung - nếu nó nhỏ hơn, xảy ra tràn. Vì vậy, phát hiện tràn sau khi tính toán đòi hỏi chỉ có một so sánh duy nhất (thực sự rất rẻ).