<style>
html, body, .ui-content {
background-color: #333;
color: #ddd;
}
body > .ui-infobar {
display: none;
}
.ui-view-area > .ui-infobar {
display: block;
}
.markdown-body h1{
color: #9CCEF2;
}
.markdown-body h2{
color: #B1D6CA;
}
.markdown-body h3{
color: #F5F6B6;
}
.markdown-body h4,
.markdown-body h5,
.markdown-body h6 {
color: #ddd;
}
.markdown-body h1,
.markdown-body h2 {
border-bottom-color: #ffffff69;
}
.markdown-body h1 .octicon-link,
.markdown-body h2 .octicon-link,
.markdown-body h3 .octicon-link,
.markdown-body h4 .octicon-link,
.markdown-body h5 .octicon-link,
.markdown-body h6 .octicon-link {
color: #fff;
}
.markdown-body img {
background-color: transparent;
}
.ui-toc-dropdown .nav>.active:focus>a, .ui-toc-dropdown .nav>.active:hover>a, .ui-toc-dropdown .nav>.active>a {
color: white;
border-left: 2px solid white;
}
.expand-toggle:hover,
.expand-toggle:focus,
.back-to-top:hover,
.back-to-top:focus,
.go-to-bottom:hover,
.go-to-bottom:focus {
color: white;
}
.ui-toc-dropdown {
background-color: #333;
}
.ui-toc-label.btn {
background-color: #191919;
color: white;
}
.ui-toc-dropdown .nav>li>a:focus,
.ui-toc-dropdown .nav>li>a:hover {
color: white;
border-left: 1px solid white;
}
.markdown-body blockquote {
color: #bcbcbc;
}
.markdown-body table tr {
background-color: #5f5f5f;
}
.markdown-body table tr:nth-child(2n) {
background-color: #4f4f4f;
}
.markdown-body code,
.markdown-body tt {
color: #eee;
background-color: rgba(230, 230, 230, 0.36);
}
a,
.open-files-container li.selected a {
color: #5EB7E0;
}
</style>
###### tags: `雜~~瓦魯多~~筆記`
# 溢位？
上課時講過ㄉ，如果用int存取大於 $2^{31}-1$ ，或是小於 $-2^{31}$ ，那就會發生「溢位」。
那「溢位」又是啥嘞？
[TOC]
## 資料型態與範圍
在這裡，我們先來複習一下各個型別可以儲存的大小：
* `int` ：$-2^{31} \le$ `int` $\lt 2^{31}$
（ $-2,147,483,648 \le$ `int` $\le 2,147,483,647$ ）
* `long long` ：$2^{63} \le$ `long long` $\lt 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$ ，如下：
```cpp=
int n = 2147483647;
```
`n` 目前儲存的已經是 `int` 的上限了，這時候我們加上以下的程式，然後讓它輸出看看：
```cpp=
int n = 2147483647;
n += 1; //使n儲存的值加1
cout << n; //輸出n
```
輸出如下：
```
-2147483648
```
可以看到， `n` 的值從 `int` 最大值加一之後，竟然跳回到 `int` 最小值了！
事實上這就是**溢位**，超出範圍的整數會再跑到另一端，並且從另一端繼續計算。
這也就是為什麼，有些題目做出來的結果會突然變成一個很小的負數。
那正是因為溢位之後，這個變數值又回到 `int` 最小值，也就是一個很大的負數（$-2,147,483,648$）從頭計算了。
## 一些避免溢位的方法
### 求平均
給定 `a` 與 `b` 兩正整數，求 `a` 與 `b` 的平均值。
最直覺的做法大概是這樣：
```cpp=
int a,b; //宣告整數變數a與b
cin >> a >> b; //輸入a與b
cout << (a+b) / 2; //輸出 (a加上b 再除以2) 的值
```
但是這樣有個問題， `(a+b)` 這東西有機會超過 `int` 的範圍，然後就會造成溢位。
所以更好的寫法應該如下：
```cpp=
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 (駭客題)](https://zerojudge.tw/ShowProblem?problemid=c221)
本題要求輸出一組 `a` 與 `b` ，作為以下程式的輸入，使以下程式執行的結果錯誤。
```cpp=
#include<bits/stdc++.h> //可以先當成是跟iostream功能一樣
using namespace std; //有興趣再去了解「標頭檔」與「bits/stdc++.h」
int main(){
int a,b;
cin>>a>>b;
cout<<a+b<<'\n';
}
```
:::spoiler <font color="FEA0A0">**解答**</font>
這題就是在考溢位的觀念。
只要讓 `a+b` 的值大於 $2,147,483,647$ ，或是小於 $-2,147,483,648$ 就行了。
:::
## 小結
其實以目前來說會遇到的題目，都不至於大到超過 `long long` 的範圍，要是真的卡在 `WA 90%` 之類的測資過不去，那可以考慮先把 `int` 都換成 `long long` 試試看。
如果還是不夠的話，那就再試試 `unsigned long long` 吧？
~~如果還是還是不夠的話，那就只能手刻大數了吧？但那又是後話了。~~
Sign in with Wallet
Connect another wallet