一、為什么會溢出？

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

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

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

一般而言，int 類型在 32 位操作系統(tǒng)上占用 4 個字節(jié)（32 位），在 64 位操作系統(tǒng)上占用 8 個字節(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 個字節(jié)，即 32 位，而最小的帶符號整數(shù)（-2^31）的二進(jìn)制補(bǔ)碼表示恰好對應(yīng)于 -2147483648。

二、怎樣解決？

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

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

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

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

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

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

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

C語言支持多種整型數(shù)據(jù)類型——表示有限范圍的整數(shù)。如圖所示，其中給出了“典型”32位和64位機(jī)器的取值范圍。每種類型都能用關(guān)鍵字來指定大小，這些關(guān)鍵字包括c h a r 、 s h o r t 、 l o n g char、short、longchar、short、long,同時還可以指示被表示的數(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é)分配，不同的大小所能表示的值的范圍是不同的。特別注意，這里給出來的唯一一個與機(jī)器有關(guān)的取值范圍是大小指示符long的。大多數(shù)64位的機(jī)器使用8個字節(jié)的表示。比32位機(jī)器上使用的4個字節(jié)的表示的取值范圍大的多

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

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

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

三、看個例題

求 a 的 b 次方對 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類型來表示a,b,c三個數(shù)，防止整數(shù)溢出，同時用到了快速冪算法，防止兩整數(shù)相乘的結(jié)果發(fā)生整數(shù)溢出。

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

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

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

• 這種操作通常用于判斷一個整數(shù)是奇數(shù)還是偶數(shù)。因為二進(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ù)值很大的時候就會發(fā)生溢出。

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

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

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

pow(a, b, c)

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

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

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

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

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

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

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

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

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

3. 錯誤處理：scanf() 在讀取輸入時需要注意錯誤處理，因為它不能自動處理輸入格式不匹配或類型不正確的情況。而 cin 可以檢測到輸入類型不匹配等錯誤，并提供相應(yīng)的錯誤處理機(jī)制，比如將輸入流置于錯誤狀態(tài)，清除錯誤標(biāo)志等。

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

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

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

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

最新評論