如何檢測(cè)無符號(hào)整數(shù)乘法溢出？我在C ++編寫一個(gè)程序來找到所有的解決方案一b = c ^，其中一個(gè)，b和c ^一起使用所有的數(shù)字0-9只出現(xiàn)一次。該方案在循環(huán)值一和b，這一個(gè)數(shù)字計(jì)數(shù)例行每次跑了一個(gè)，b和一個(gè)b以檢查是否數(shù)字的條件感到滿意。然而，當(dāng)可以產(chǎn)生偽解一個(gè)b溢出整數(shù)限制。我最終使用以下代碼檢查：unsigned long b, c, c_test;...c_test=c*b;
// Possible overflowif (c_test/b != c) {/* There has been an overflow*/}else c=c_test; // No overflow有沒有更好的方法來測(cè)試溢出？我知道有些芯片有一個(gè)內(nèi)部標(biāo)志，當(dāng)溢出發(fā)生時(shí)會(huì)設(shè)置，但我從未見過通過C或C ++訪問它。請(qǐng)注意，在C和C ++中，簽名 int溢出是未定義的行為，因此您必須在不實(shí)際導(dǎo)致它的情況下檢測(cè)它。有關(guān)添加前的signed int overflow，請(qǐng)參閱在C / C ++中檢測(cè)帶符號(hào)的溢出。
4 回答
慕村9548890
TA貢獻(xiàn)1884條經(jīng)驗(yàn) 獲得超4個(gè)贊
有是一種方法來確定操作是否可能溢出，使用操作數(shù)的最顯著一個(gè)位和一點(diǎn)點(diǎn)基本的二進(jìn)制數(shù)學(xué)知識(shí)的位置。
另外，任何兩個(gè)操作數(shù)將導(dǎo)致（最多）比最大操作數(shù)的最高一位多一位。例如：
bool addition_is_safe(uint32_t a, uint32_t b) {
size_t a_bits=highestOneBitPosition(a), b_bits=highestOneBitPosition(b);
return (a_bits<32 && b_bits<32);}對(duì)于乘法，任何兩個(gè)操作數(shù)將導(dǎo)致（最多）操作數(shù)的位總和。例如：
bool multiplication_is_safe(uint32_t a, uint32_t b) {
size_t a_bits=highestOneBitPosition(a), b_bits=highestOneBitPosition(b);
return (a_bits+b_bits<=32);}同樣，您可以估算結(jié)果的最大大小a，b如下所示：
bool exponentiation_is_safe(uint32_t a, uint32_t b) {
size_t a_bits=highestOneBitPosition(a);
return (a_bits*b<=32);}（當(dāng)然，替換目標(biāo)整數(shù)的位數(shù)。）
我不確定以最快的方式確定數(shù)字中最高的一位的位置，這是一種強(qiáng)力方法：
size_t highestOneBitPosition(uint32_t a) {
size_t bits=0;
while (a!=0) {
++bits;
a>>=1;
};
return bits;}它并不完美，但是在你進(jìn)行操作之前，這會(huì)讓你知道任何兩個(gè)數(shù)字是否會(huì)溢出。我不知道它是否比簡(jiǎn)單地以你建議的方式檢查結(jié)果更快，因?yàn)?code>highestOneBitPosition函數(shù)中的循環(huán)，但它可能（特別是如果你事先知道操作數(shù)中有多少位）。
慕容森
TA貢獻(xiàn)1853條經(jīng)驗(yàn) 獲得超18個(gè)贊
Clang 3.4+和GCC 5+提供經(jīng)過檢查的算術(shù)內(nèi)置函數(shù)。它們?yōu)檫@個(gè)問題提供了一個(gè)非?？焖俚慕鉀Q方案，特別是與比特測(cè)試安全檢查相比。
對(duì)于OP問題中的示例，它可以這樣工作：
unsigned long b, c, c_test;if (__builtin_umull_overflow(b, c, &c_test)){
// returned non-zero: there has been an overflow}else{
// return zero: there hasn't been an overflow}c_test如果發(fā)生溢出，Clang文檔沒有指定是否包含溢出的結(jié)果，但GCC文檔說它確實(shí)存在溢出。鑒于這兩者似乎是__builtin兼容的，可以安全地假設(shè)這也是Clang的工作方式。
__builtin對(duì)于int大小，長(zhǎng)大小和長(zhǎng)long大小，每個(gè)算術(shù)運(yùn)算都有一個(gè)可以溢出（加法，減法，乘法），帶有符號(hào)和無符號(hào)變量。該名稱的語法是__builtin_[us](operation)(l?l?)_overflow：
u對(duì)于未簽名或s對(duì)簽名的 ;操作是其中之一
add，sub或mul;沒有
l后綴意味著操作數(shù)是ints; 一個(gè)l手段long; 兩個(gè)l意思是long long。
因此，對(duì)于已檢查的帶符號(hào)長(zhǎng)整數(shù)，它將是__builtin_saddl_overflow。完整列表可以在Clang文檔頁面上找到。
GCC 5+和鏘3.8+另外提供，如果沒有指定值的類型工作的通用內(nèi)建的：__builtin_add_overflow，__builtin_sub_overflow和__builtin_mul_overflow。這些也適用于小于的類型int。
內(nèi)置程序降低到平臺(tái)最佳狀態(tài)。在x86上，它們檢查進(jìn)位，溢出和符號(hào)標(biāo)志。
Visual Studio的cl.exe沒有直接的等價(jià)物。對(duì)于無符號(hào)加法和減法，包括<intrin.h>允許你使用addcarry_uNN和subborrow_uNN（其中NN是位數(shù)，如addcarry_u8或subborrow_u64）。他們的簽名有點(diǎn)遲鈍：
unsigned char _addcarry_u32(unsigned char c_in, unsigned int src1, unsigned int src2, unsigned int *sum); unsigned char _subborrow_u32(unsigned char b_in, unsigned int src1, unsigned int src2, unsigned int *diff);
c_in/ b_in是輸入的進(jìn)位/借位標(biāo)志，返回值是輸出的進(jìn)位/借位。它似乎沒有簽名操作或乘法的等價(jià)物。
否則，Clang for Windows現(xiàn)在可以投入生產(chǎn)（對(duì)Chrome來說已經(jīng)足夠了），所以這也是一個(gè)選擇。
SMILET
TA貢獻(xiàn)1796條經(jīng)驗(yàn) 獲得超4個(gè)贊
有些編譯器可以訪問CPU中的整數(shù)溢出標(biāo)志，然后可以測(cè)試，但這不是標(biāo)準(zhǔn)的。
您還可以在執(zhí)行乘法之前測(cè)試溢出的可能性：
if ( b > ULONG_MAX / a ) // a * b would overflow
- 4 回答
- 0 關(guān)注
- 1612 瀏覽
添加回答
舉報(bào)
0/150
提交
取消