一、為什么會(huì)溢出？

整數(shù)乘積的溢出問(wèn)題是指兩個(gè)整數(shù)相乘得到的結(jié)果超過(guò)了所能表示的數(shù)據(jù)類型的范圍。

在計(jì)算機(jī)中，整數(shù)的表示是有限的，即存在一個(gè)最大值和最小值。當(dāng)進(jìn)行乘法運(yùn)算時(shí)，如果結(jié)果超出了整數(shù)的表示范圍，就會(huì)發(fā)生溢出。這種情況下，計(jì)算結(jié)果將不再準(zhǔn)確，并且可能導(dǎo)致數(shù)據(jù)丟失或錯(cuò)誤的計(jì)算結(jié)果。

比如：int類型，C 語(yǔ)言標(biāo)準(zhǔn)規(guī)定了 int 類型必須至少能表示 -32767 到 32767 之間的整數(shù)，也就是說(shuō)，int 類型的最小值和最大值范圍為 -215 到 215-1。

一般而言，int 類型在 32 位操作系統(tǒng)上占用 4 個(gè)字節(jié)（32 位），在 64 位操作系統(tǒng)上占用 8 個(gè)字節(jié)（64 位）。使用 limits.h 頭文件可以查看當(dāng)前編譯器中 int 類型的最大值和最小值。

#include<iostream>
#include <limits.h>
using namespace std;

int main()
{
    printf("INT_MIN: %d\n", INT_MIN);
    printf("INT_MAX: %d\n", INT_MAX);

    system("pause");
    return 0;
} 

至于INT_MIN的值為什么是-2147483648，原因是：

在 32 位系統(tǒng)中，int 類型通常占據(jù) 4 個(gè)字節(jié)，即 32 位，而最小的帶符號(hào)整數(shù)（-2^31）的二進(jìn)制補(bǔ)碼表示恰好對(duì)應(yīng)于 -2147483648。

二、怎樣解決？

可以使用更大范圍的整數(shù)類型，比如 long long 或者 int64_t 等，以支持更大范圍的數(shù)值計(jì)算。

根據(jù)取值范圍，靈活選用整數(shù)類型：

32位程序上C語(yǔ)言整型數(shù)據(jù)類型的典型取值范圍

64位程序上C語(yǔ)言整型數(shù)據(jù)類型的典型取值范圍

圖中的注意事項(xiàng)：
取值范圍不是對(duì)稱的———負(fù)數(shù)的范圍比整數(shù)的范圍大1.當(dāng)我們考慮如何表示負(fù)數(shù)的時(shí)候，會(huì)看到為什么會(huì)是這樣子。

C語(yǔ)言的整型數(shù)據(jù)類型的保證的取值范圍。C語(yǔ)言標(biāo)準(zhǔn)要求這些數(shù)據(jù)類型必須至少具有這樣的取值范圍

C語(yǔ)言標(biāo)準(zhǔn)定義了每種數(shù)據(jù)類型必須能夠表示的最小的取值范圍。如上圖所示，它的取值范圍與32位和64位所示的典型實(shí)現(xiàn)一樣或者小一些。特別地，除了固定大小的數(shù)據(jù)類型是例外，我們看到它們只要求正數(shù)和負(fù)數(shù)的取值范圍是對(duì)稱的。此外，數(shù)據(jù)類型int可以用2個(gè)字節(jié)的數(shù)字來(lái)實(shí)現(xiàn)。這幾乎退到了16位機(jī)器的時(shí)代。還可以看到，long的大小可以用4個(gè)字節(jié)的數(shù)字來(lái)實(shí)現(xiàn)，對(duì)32位程序來(lái)說(shuō)這是很典型的。固定大小的數(shù)據(jù)類型保證數(shù)值的范圍與32位程序上C語(yǔ)言整型數(shù)據(jù)類型的典型取值范圍一致。包括負(fù)數(shù)與正數(shù)的不對(duì)稱性。

C語(yǔ)言支持多種整型數(shù)據(jù)類型——表示有限范圍的整數(shù)。如圖所示，其中給出了“典型”32位和64位機(jī)器的取值范圍。每種類型都能用關(guān)鍵字來(lái)指定大小，這些關(guān)鍵字包括c h a r 、 s h o r t 、 l o n g char、short、longchar、short、long,同時(shí)還可以指示被表示的數(shù)字是非負(fù)數(shù)（聲明為u n s i g n e d unsignedunsigned），或者可能是負(fù)數(shù)（默認(rèn)即可）。為這些不同的大小分配的字節(jié)數(shù)可根據(jù)程序編譯為32位gcc -m32 prog.c或者64位gcc -m64 prog.c而有所不同。根據(jù)字節(jié)分配，不同的大小所能表示的值的范圍是不同的。特別注意，這里給出來(lái)的唯一一個(gè)與機(jī)器有關(guān)的取值范圍是大小指示符long的。大多數(shù)64位的機(jī)器使用8個(gè)字節(jié)的表示。比32位機(jī)器上使用的4個(gè)字節(jié)的表示的取值范圍大的多

補(bǔ)充：字?jǐn)?shù)據(jù)大小

每臺(tái)計(jì)算機(jī)都有一個(gè)字長(zhǎng)（word size），指明指針數(shù)據(jù)的標(biāo)稱大?。╪ominal size）。
因?yàn)樘摂M地址是以這樣的一個(gè)字來(lái)編碼的，所以字長(zhǎng)決定的最重要的系統(tǒng)參數(shù)就是虛擬地址空間的最大大小。也就是說(shuō)，對(duì)于一個(gè)字長(zhǎng)為w ww位的機(jī)器而言，虛擬地址的范圍位0 − 2 w − 1 0 - 2^w-10−2w−1,程序最多訪問(wèn)2 w 2^w2w個(gè)字節(jié)
最近這些年，出現(xiàn)了大規(guī)模的從32位字長(zhǎng)機(jī)器到64位字長(zhǎng)機(jī)器的遷移。這種情況首先出現(xiàn)在為大型科學(xué)和數(shù)據(jù)庫(kù)應(yīng)用設(shè)計(jì)的高端機(jī)器上，之后是臺(tái)式機(jī)和筆記本電腦，最近則出現(xiàn)在智能手機(jī)的處理器上。32位字長(zhǎng)限制虛擬地址空間為4千兆字節(jié)（寫作4GB），也就是說(shuō)，剛剛超過(guò)4 × 1 0 9 4\times10^94×109個(gè)字節(jié)。擴(kuò)展到64位字長(zhǎng)使得虛擬地址空間為16EB，大約是1.84 × 1 0 19 1.84\times 10^{19}1.84×1019字節(jié)

基本c數(shù)據(jù)類型的典型大小（以字節(jié)為單位）。分配的字節(jié)數(shù)受如何編譯的影響而變化。

三、看個(gè)例題

求 a 的 b 次方對(duì) p 取模的值，其中 0≤a,b,c≤109, c>0

• 用c++寫：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll a,b,c;

int main(){
    cin >> a >> b >> c;
    ll ans = 1;
    while (b) {
        if(b&1) {
            ans = ans * a % c;
        } 
        a = a * a % c;
        b /= 2;  // 將指數(shù)右移一位
    }
    cout << ans % c << endl;
    
    return 0;
}

這里用long long類型來(lái)表示a,b,c三個(gè)數(shù)，防止整數(shù)溢出，同時(shí)用到了快速冪算法，防止兩整數(shù)相乘的結(jié)果發(fā)生整數(shù)溢出。

快速冪算法通過(guò)對(duì)指數(shù) y 進(jìn)行二進(jìn)制拆分，將指數(shù)的冪運(yùn)算轉(zhuǎn)化為多個(gè)底數(shù)的平方運(yùn)算，從而減少了計(jì)算次數(shù)，提高了算法效率。

• 在 C 和 C++ 中，y & 1 表示對(duì)變量 y 的值和二進(jìn)制數(shù) 1 進(jìn)行按位與（AND）操作。具體來(lái)說(shuō)，這個(gè)表達(dá)式會(huì)將 y 的二進(jìn)制表示的最低位與 1 進(jìn)行按位與運(yùn)算，得到的結(jié)果為 0 或 1。

• 如果 y 的最低位是 1，那么 y & 1 的結(jié)果就是 1；如果 y 的最低位是 0，那么 y & 1 的結(jié)果就是 0。

• 這種操作通常用于判斷一個(gè)整數(shù)是奇數(shù)還是偶數(shù)。因?yàn)槎M(jìn)制數(shù)的最低位為 1 表示奇數(shù)，為 0 表示偶數(shù)，所以 y & 1 可以快速判斷 y 是奇數(shù)還是偶數(shù)。

• c的寫法： （和c++只有一點(diǎn)點(diǎn)區(qū)別，文末補(bǔ)充）

#include<stdio.h>
int main(){
	long long a,b,c,d=1;
	scanf("%ld %ld %ld",&a,&b,&c);
	while(b){
		if(b&1)	d=d*a%c;
		a=a*a%c;
		b>>=1;
	}
	printf("%ld",d%c);
}

• python的寫法

a, b, c = map(int, input().split())
print(pow(a, b, c))

但是如果python以下寫法，數(shù)值很大的時(shí)候就會(huì)發(fā)生溢出。

a, b, c = map(int, input().split())
ans = pow(a, b) % c
print(ans)

雖然Python 中的整數(shù)類型是動(dòng)態(tài)的，不會(huì)存在固定的最大值，但如果結(jié)果超出了 Python 能表示的范圍，也會(huì)發(fā)生溢出。就比如pow(a, b) % c這一步，當(dāng)a, b, c 很大的時(shí)候，也是會(huì)發(fā)生整數(shù)溢出。

但是python有個(gè)很方便的函數(shù)，就是pow()的用法

pow(a, b, c)

具體參數(shù)含義如下：
a：底數(shù)
b：指數(shù)
c：模數(shù)

這個(gè)函數(shù)返回值為 (a**b) % c 的結(jié)果。

這個(gè)函數(shù)返回值為 (a**b) % c 的結(jié)果。

例如，pow(2, 3, 5) 將返回 3，因?yàn)?2 的 3 次方是 8，然后對(duì) 5 取模的結(jié)果是 3。

pow(a, b, c)函數(shù)在需要進(jìn)行大數(shù)運(yùn)算并對(duì)結(jié)果取模的情況下非常有用。

四、補(bǔ)充：scanf和cin的區(qū)別

scanf() 是 C 語(yǔ)言中的輸入函數(shù)，而 cin 是 C++ 中的輸入流對(duì)象。它們之間有以下幾個(gè)區(qū)別：

1. 語(yǔ)言：scanf() 是 C 語(yǔ)言的函數(shù)，而 cin 是 C++ 的輸入流對(duì)象。

2. 輸入方式：scanf() 是使用格式化字符串來(lái)指定輸入格式，可以通過(guò)不同的格式說(shuō)明符（如 %d、%f、%s 等）來(lái)讀取不同類型的數(shù)據(jù)。而 cin 使用運(yùn)算符重載和類型推斷來(lái)直接從標(biāo)準(zhǔn)輸入流中讀取數(shù)據(jù)，不需要顯式指定輸入格式。

3. 錯(cuò)誤處理：scanf() 在讀取輸入時(shí)需要注意錯(cuò)誤處理，因?yàn)樗荒茏詣?dòng)處理輸入格式不匹配或類型不正確的情況。而 cin 可以檢測(cè)到輸入類型不匹配等錯(cuò)誤，并提供相應(yīng)的錯(cuò)誤處理機(jī)制，比如將輸入流置于錯(cuò)誤狀態(tài)，清除錯(cuò)誤標(biāo)志等。

4. 輸入緩沖：scanf() 函數(shù)對(duì)輸入的處理是基于緩沖區(qū)的，它會(huì)將輸入數(shù)據(jù)讀取到緩沖區(qū)中，然后根據(jù)格式字符串進(jìn)行解析。而 cin 對(duì)象則是基于流的輸入，它會(huì)逐個(gè)字符地從輸入流中讀取并解析數(shù)據(jù)，不需要緩沖區(qū)。

5. 輸入分隔符：scanf() 默認(rèn)以空格、制表符、換行符等作為輸入分隔符，可以通過(guò)格式化字符串來(lái)指定不同的分隔符。而 cin 默認(rèn)以空格、制表符、換行符等作為輸入分隔符，但它還提供了更靈活的方式來(lái)處理不同的輸入分隔符。

總的來(lái)說(shuō)，scanf() 是 C 語(yǔ)言中的函數(shù)，使用格式化字符串來(lái)指定輸入格式，而 cin 是 C++ 中的輸入流對(duì)象，使用運(yùn)算符重載和類型推斷來(lái)直接從標(biāo)準(zhǔn)輸入流中讀取數(shù)據(jù)，并提供更靈活的錯(cuò)誤處理機(jī)制。兩者在輸入方式、錯(cuò)誤處理、緩沖處理和輸入分隔符上有所不同。

以上就是C/C++整數(shù)乘積的溢出問(wèn)題的解決的詳細(xì)內(nèi)容，更多關(guān)于C/C++整數(shù)及乘積溢出的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章！

最新評(píng)論