一、為什么會溢出？

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

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

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

一般而言，int 類型在 32 位操作系統(tǒng)上占用 4 個字節(jié)（32 位），在 64 位操作系統(tǒng)上占用 8 個字節(jié)（64 位）。使用 limits.h 頭文件可以查看當前編譯器中 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 類型通常占據 4 個字節(jié)，即 32 位，而最小的帶符號整數（-2^31）的二進制補碼表示恰好對應于 -2147483648。

二、怎樣解決？

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

根據取值范圍，靈活選用整數類型：

32位程序上C語言整型數據類型的典型取值范圍

64位程序上C語言整型數據類型的典型取值范圍

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

C語言的整型數據類型的保證的取值范圍。C語言標準要求這些數據類型必須至少具有這樣的取值范圍

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

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

補充：字數據大小

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

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

三、看個例題

求 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;  // 將指數右移一位
    }
    cout << ans % c << endl;
    
    return 0;
}

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

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

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

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

• 這種操作通常用于判斷一個整數是奇數還是偶數。因為二進制數的最低位為 1 表示奇數，為 0 表示偶數，所以 y & 1 可以快速判斷 y 是奇數還是偶數。

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

#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以下寫法，數值很大的時候就會發(fā)生溢出。

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

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

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

pow(a, b, c)

具體參數含義如下：
a：底數
b：指數
c：模數

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

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

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

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

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

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

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

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

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

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

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

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

以上就是C/C++整數乘積的溢出問題的解決的詳細內容，更多關于C/C++整數及乘積溢出的資料請關注腳本之家其它相關文章！

最新評論