tags: 雜~~瓦魯多~~筆記

溢位？

上課時講過ㄉ，如果用int存取大於

$2^{31}-1$ ，或是小於

$-2^{31}$ ，那就會發生「溢位」。

那「溢位」又是啥嘞？

• 溢位？
  • 資料型態與範圍
  • 溢位
  • 一些避免溢位的方法
    • 求平均
  • 參考題目與詳解
  • 小結

資料型態與範圍

在這裡，我們先來複習一下各個型別可以儲存的大小：

• int ：

  $-2^{31}\le$ int
  $<2^{31}$
  （
  $-2,147,483,648\le$ int
  $\le 2,147,483,647$　）

• long long ：

  $2^{63}\le$ long long
  $<2^{63}$
  （　
  $2^{63}-1=9,223,372,036,854,775,807\approx 9\times {10}^{18}$　）

（其實還有個 unsigned long long ，範圍是0 ~ long long 的兩倍，但要用到那麼大的也不常見。）

超過這個範圍，不論太大或太小都會產生溢位。

溢位

進入正題！

假設今天有個 int 型態的變數 n，它現在儲存的值是

$2,147,483,647$ ，如下：

int n = 2147483647;

n 目前儲存的已經是 int 的上限了，這時候我們加上以下的程式，然後讓它輸出看看：

int n = 2147483647;
n += 1;    //使n儲存的值加1

cout << n; //輸出n

輸出如下：

-2147483648

可以看到， n 的值從 int 最大值加一之後，竟然跳回到 int 最小值了！

事實上這就是溢位，超出範圍的整數會再跑到另一端，並且從另一端繼續計算。

這也就是為什麼，有些題目做出來的結果會突然變成一個很小的負數。
那正是因為溢位之後，這個變數值又回到 int 最小值，也就是一個很大的負數（

$-2,147,483,648$）從頭計算了。

一些避免溢位的方法

求平均

給定 a 與 b 兩正整數，求 a 與 b 的平均值。

最直覺的做法大概是這樣：

int a,b;           //宣告整數變數a與b
cin >> a >> b;     //輸入a與b

cout << (a+b) / 2; //輸出 (a加上b 再除以2) 的值

但是這樣有個問題， (a+b) 這東西有機會超過 int 的範圍，然後就會造成溢位。

所以更好的寫法應該如下：

int a,b;               //宣告整數變數a與b
cin >> a >> b;         //輸入a與b

cout << a + (b-a) / 2; //輸出 (a 加上 b減a再除以2) 的值

這樣就可以用 (b-a) 來避免 (a+b) 可能超出範圍的問題了。

參考題目與詳解

Zerojudge c221: A+B problem (駭客題)

本題要求輸出一組 a 與 b ，作為以下程式的輸入，使以下程式執行的結果錯誤。

#include<bits/stdc++.h> //可以先當成是跟iostream功能一樣
using namespace std;    //有興趣再去了解「標頭檔」與「bits/stdc++.h」

int main(){
    int a,b;
    cin>>a>>b;
    cout<<a+b<<'\n';
}

解答

這題就是在考溢位的觀念。

只要讓 a+b 的值大於

$2,147,483,647$ ，或是小於

$-2,147,483,648$ 就行了。

小結

其實以目前來說會遇到的題目，都不至於大到超過 long long 的範圍，要是真的卡在 WA 90% 之類的測資過不去，那可以考慮先把 int 都換成 long long 試試看。
如果還是不夠的話，那就再試試 unsigned long long 吧？

如果還是還是不夠的話，那就只能手刻大數了吧？但那又是後話了。