目錄
- 問題
- 原理
- 奇怪的回圈
- 計算機的編碼
- 回圈的產生
- 如何識別溢位
- 乘法
- 加法
- 參考文獻
問題
在執行乘法時（ i ! ? 2 i , ( i = 0 , 1 , . . . , n ? 1 ) i!*2^{i},(i=0,1,...,n-1) i!?2i,(i=0,1,...,n?1)），當計算的值超過了int上限后卻變成了負數，
原理
奇怪的回圈
int的范圍是：-2147483648~2147483647
如果超出這個范圍會出現回圈；也就是最大的數+1變成了最小的數，最小的數-1又成了最大的數，所有的數就像模運算一樣形成了回圈，
如:-2147483648-1=2147483647;2147483647+1=-2147483648
可以看到在INT_MAX后做累加，就回到了INT_MIN，
計算機的編碼
對于一個數, 計算機要使用一定的編碼方式進行存盤. 原碼, 反碼, 補碼是機器存盤一個具體數字的編碼方式，上面的回圈就是計算機采用的特殊編碼造成的，下面分別做介紹，
1，原碼
一開始人們是通過原碼來表示整數，整數有正負之分，便通過符號位+二進制的方式表示，（最高位（最左邊）取0表示正數，取1表示負數，然后加上對應的二進制，）
+1 = 0000 0001
-1 = 1000 0001
2，反碼
正數的反碼是其本身
負數的反碼是在其原碼的基礎上, 符號位不變，其余各個位取反.
[+1] = [00000001]原 = [00000001]反
[-1] = [10000001]原 = [11111110]反
3，補碼
正數的補碼就是其本身
負數的補碼是在其原碼的基礎上, 符號位不變, 其余各位取反, 最后+1. (即在反碼的基礎上+1)
[+1] = [00000001]原 = [00000001]反 = [00000001]補
[-1] = [10000001]原 = [11111110]反 = [11111111]補
4，為何選擇補碼
現代的計算機底層是采用補碼來對整數編碼，這是因為補碼能夠極大的簡化運算，
對于計算機, 加減乘數已經是最基礎的運算, 要設計的盡量簡單.，于是人們想出了將符號位也參與運算的方法. 我們知道, 根據運演算法則減去一個正數等于加上一個負數, 即: 1-1 = 1 + (-1) = 0 , 所以機器可以只有加法而沒有減法, 這樣計算機運算的設計就更簡單了.
使用原碼和反碼讓符號位也參與計算,都會產生錯誤
1 - 1 = 1 + (-1) = [00000001]原 + [10000001]原 = [10000010]原 = -2
1 - 1 = 1 + (-1) = [0000 0001]反 + [1111 1110]反 = [1111 1111]反 = [1000 0000]原 = -0
而使用補碼則不會有這個問題
1-1 = 1 + (-1) = [0000 0001]補 + [1111 1111]補 = [0000 0000]補=0
此外使用補碼還能多表示一個負數
0用[0000 0000]表示, 而以前出現問題的-0則不存在了.可以用[1000 0000]表示-128.
這就是為什么現在32位的int范圍是-2147483648~2147483647
回圈的產生
INT的最大值2147483647的二進制是：
1111111111111111111111111111111
2147483648的二進制是：
10000000000000000000000000000000
換成補碼：
0 00000000000000000000000000000000（INTMAX)
0 0111111111111111111111111111111111111(INTMAX+1，溢位了1位)
因為INT只支持32位，就多出來了1位，計算機默認會截除掉最高位（最左邊），
則INTMAX+1的補碼就變成了：
0 111111111111111111111111111111111111=-2147483647
計算機巧妙的利用這一點在溢位后達成了一個回圈
如何識別溢位
乘法
設int a, b;
ab>INTMAX 顯然是無法判斷出結果的（溢位了就從負數開始回圈），
換個思路使用b>INTMAX/a
就是把溢位的ab拆分為未溢位的a和b，然后執行除法來判斷是否溢位，
本問題的判斷就可以修改如下：
int algo(int n, int a[])
{
a[0] = 0;
a[1] = 2;
for (int i = 2; i < n; i++)
{
a[i] = 2 * i * a[i - 1];
//if (a[i-1] > INT_MAX / (2*i))
if(0)
{
printf("a[i]:%d\n", i);
printf("堆疊上溢，按出錯處理！");
exit(OVERFLOW);
}
}
return OK;
}
加法
例：檢查兩個非負整型變數a+b是否溢位
第一種：if(a+b < 0)
這種做法是檢查內部暫存器的標志位是否為負
第二種： if((unsigned)a +(unsigned)b >INT_MAX)
這種做法是強制將a和b都強制轉換成無符號整數
第三種： if(a > INT_MAX - b)
這種做法不需要用到無符號算術運算子，也和我們之前乘法的處理類似
參考文獻
[1]https://blog.csdn.net/weixin_33898233/article/details/92355647.
[2]https://blog.csdn.net/shun_smile/article/details/80042210.
[3]https://blog.csdn.net/zl10086111/article/details/80907428.
[4]https://zhuanlan.zhihu.com/p/340095782.
[5]https://blog.csdn.net/WmxL56/article/details/38380627.
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/277501.html
標籤：其他
上一篇：ELK7.12.0環境搭建教程
下一篇：命令列語法錯誤