前言
在程式中,我們經常會涉及到數值計算操作,比如從最簡單的數值的表示,到加、減、乘除,再到移位等等,而對于這些往往我們都信心十足,常常用直覺告訴自己:這麼做沒錯!但是,計算機并不是靠直覺來感覺數值的,它可是個很嚴謹的家夥,如果你隻是用直覺告訴它你要做的事,那麼它也會告訴你:哼!想要我幫你做事情,那麼就按我的規則來吧! 想要知道計算機有哪些規則?那好,本篇就帶你了解計算機關于資訊表示和處理内容,但我們絕不是簡單的了解,我同時還會揭開隐藏在數值計算中的陷阱,這樣,在以後的編碼過程中,我們就能避免可能的風險。
你可能會某一個瞬間蒙頭寫下如下代碼intn =500*400*200*300;然後執行後發現結果居然是個負值,或者苦苦的等待循環退出。可能再回去看的時候才恍然大悟,哦,溢出了。亦或者你不明白這兩個表達式的結果為什麼不同?(3.14+1e20)-le20 ,3.14+(le20-le20).又或者意想類似這樣的表達式會始終成立x*x>0,(x>0)||(x-1)<0, x<0 || -x>=0。噢,你可能會說從沒遇到過這樣的場景,或者說從來都是假設資料在一定的範圍之内的,不會取到那麼極端的資料。更何況那樣的表達式不一定會用的到。我們會這麼想,假設在資料取值的範圍内,我們的計算沒有任何差錯,我們就以為程式是沒有問題,而其實這離程式的”絕對正确”還差一步。你可能會反駁,追求絕對的正确有意義?我們始終能夠滿足業務要求就是正确的?更何況你那出現的情況幾乎是不可能的?可能,我們還沒遇到過由于數值計算的誤差所帶來的風險和損失,或者由于計算機某一程式的算術計算的微妙細節而産生的計算機安全漏洞,最終被黑客所利用。是的,這些情況出現的機率很低,但我們有必要深究保證程式的絕對正确,有必要深究數值計算的細節,因為關乎我們程式的正确性和安全性。
整數編碼
我們先看C語言中支援的整數類型和它對應的取值範圍:
說明:C語言标準隻是定義了每種資料類型必須能夠表示的最小的取值範圍。
1. 無符号數的編碼
假設一個整數資料類型有w位,位向量為x=[xw-1,xw-2,…..,x0]表示向量中的每一位,那麼我們用下面的公式來表示無符号數:
其中B2Uw的範圍{0,…….2w-1},最大值為UMaxw= 2w-1.
2. 補碼編碼
在計算機中,最常見的有符号數的負數值就是通過補碼來表示的。同樣我們也能給出補碼的公式:
公式中最高有效為xw-1稱為符号位,它的權重為-2w-1.符号位為1表示為負,否則為正數,下面我們看幾個例子:
明白了補碼運算,那麼,讓我們考慮下w位補碼所能表示的值得範圍。它能表示的最小值為位向量[1000…..0],其整數值為TMinw=-2w-1,而最大值為位向量[011111….1],其整數值為TMaxw =2w-1-1.
3.有符号數和無符号數的轉換
對于數值的轉換,在計算機中的處理非常簡單,假如聲明一個int型的有符号整型變量x和一個無符号整型變量u,通過u=(unsigned)x表達式,将x轉換為無符号整型。這時候x和u的位向量是完全相同的,隻是對于不同類型的整型給予不同的解釋。也就是轉換的前提條件是保持位模式不變。
那麼,對于相同的位模式x我們可以得到:
B2Uw(x)-B2Tw(x)=Xw-12w
-> B2Uw(x) = Xw-12w+ B2Tw(x)
如果令x = T2Bw(x),那麼我們就可以得到如下公式:
B2Uw(T2Bw(x))=T2Uw(x)=xw-12w+x
在x的補碼表示中,位xw-1表示x是否為負. 得到
注:x代表位向量,而x代表數值
映射關系如下:
同樣反過來我們也可以得到無符号轉換為有符号數的公式U2Tw.
映射關系如下:
3. 拓展位表示
我們經常會遇到需要将較小位向量的數值轉換為較大位向量的數值。而我們針對這樣的情況隻要記住兩個概念:零拓展和符号拓展,關于這兩個概念,請參考附錄。
4. 截斷
同樣和拓展對應的也有一個操作就是截斷,表示減少一個數值的位數。比如下面的代碼段:
Int x =53191;
short sx = (short)x;
int y =sx;
我們發現經過一次轉化x的值變成了負值。而原因就在與中間的截斷和符号拓展。
關于上面的介紹,可能你都足夠熟悉了,隻是覺得在日常的編碼中不會有多大問題,好吧,為了引起對于符号轉換的重視,我們看個例子:
Float sum(float a[],unsigned length){
Int I;
Float result = 0.0f;
For(I=0;i<=length-1;i++){
Result+=a[i];
}
Return result;
}
恩….,貌似沒有問題,當length = 0時,結果理應為0.0,但卻出人意料的得到一個存儲器讀取錯誤。細心的你可能一下就發現了問題所在,在for循環内length-1的值為UMAX,因為length為無符号整型。
可能這段代碼的錯誤還算明顯,可下面的呢?你想通過調用strlen函數來判斷一個字元字元串是否比另一個更長。
Int strlonger(char*s,char* t){
Returnstrlen(s)-strlen(t)>0;
}
當我們取一個比字元串t還短的字元串s時,我們發現結果居然是大于0,這讓我們很吃驚。可當我們知道了strlen原型後才知道原來strlen計算傳回的是一個size_t類型的值,即unsigned int 是一個無符号整型,是以原因也就很清楚。
可能你覺得上面的代碼都還不夠現實,或者心存僥幸(我們常常都這樣L),那麼看下面的一段代碼:
#define KSIZE 1024
Char kbuf[KSIZE];
Int copy_from_kernel(void* user_dest,intmaxlen)
{
Intlen = KSIZE<maxlen ? KSIZE:maxlen;
Memcpy(user_dest,kbuf,len);
Return len;
}
這段代碼是函數getpeername實作中的一段代碼,熟悉網絡的朋友一定不陌生,這個庫函數根據給定的socket來擷取對端位址。函數copy_from_kernel是将系統核心維護的資料複制到使用者可以通路的存儲區。對于一般使用者來說,核心維護的資料是不可讀的,因為這可能包含其他使用者的和系統運作得敏感資訊,但現實的kbuf區域是使用者可讀的。參數maxlen給出了配置設定給使用者區的緩沖區長度,這個緩沖區是用user_dest訓示的。可是如果我們清楚memcpy的原型memcpy(void*dest,void*src,size_t size);就很快能反應上來,如果給maxlen傳遞一個負值,就可以通路未被授權的核心存儲器區域,進而導緻安全漏洞。
數值計算
1. 無符号加法
我們或許都曾驚奇的發現,兩個正數x和y相加的值為負;表達式x<y與x-y<0的結果并不都是一緻。對于兩個非負整數0<=x,y<=2w-1,我們就有一個可能的範圍0<=x+y<=2w+1-2,這個和可能需要w+1位。一般的,如果x+y<2w,那麼w+1位為0,丢棄這個值并不影響結果,可如果2w<=x+y<2w+1,那麼w+1位的值會為1,丢棄這個值就相當于減去了2w,是以得到下面的結論:
那麼對于x+y=s的結果我們怎麼判斷s是否溢出?答案就是當且僅當s<x或者y<s時,發生了溢出。因為如果x+y溢出s就可以表示為s=x+y-2w,而y或者x滿足x<2w,y<2w.
那麼s=x+(y-2w)<x或者s=y+(x-2w)<y。
2. 補碼加法
對于補碼加法,在給定範圍-2w-1<=x,y<=2w-1-1的整數x和y,他們的和就在範圍-2w<=x+y<=2w-2。這可能也需要w+1位。
我們可以對補碼加法運算得到下面的公式:
同樣我們怎麼判斷x+y是否溢出呢?
Int tadd_ok(int x,int y){
Int sum =x+y;
Intneg_over = x<0 && y<0 && sum>=0;
Intpos_over = x>=0&&y>=0&&sum<0
Return !neg_over&&!pos_over;
}
沒錯,上面的代碼就是按照補碼加法的溢出規則寫出來的,即兩個負數相加得到非負值,兩個非負值相加得到一個負值,當然,你從上面的映射圖看到的更加明顯。可能你會覺得上面的代碼太過備援,那麼還有另一個可行的方法就是将通過對兩個待相加數進行異或,并判斷結果最高位的是否和其中一個的加數的最高位符号一緻。
3. 補碼的非
範圍在-2w-1<=x<2w-1中的每個數字x都有一個加法逆元(見附錄),首先對于x!=-2w-1,我們可以看到它的加法逆元就是-x,而對于x =-2w-1=TMinw,-x=2w-1不能表示為一個w位的數。
而其位模式是和-2w-1相同的,是以他的加法逆元實際上就是他本身。是以對于範圍
-2w-1<=x<2w-1内的x,補碼的非運算公式為:
4. 無符号乘法
範圍在0<=x,y<=2w-1内的整數x和y可以表示 為w位的無符号數,但它們的乘積x*y的取值範圍為0到(2w-1)=22w-2w+1+1之間。C語言中無符号乘法被定義為産生w位的值,就是2w位的整數乘積的低w位表示的值。是以無符号乘法運算的結果為:
X*y =(x*y) mod 2w
5. 補碼乘法
範圍在-2w-1<=x,y<2w-1-1内的整數x和y可以表示為w位的補碼數字,但是他們的乘積
X*y的取值範圍在-2w-1*(2w-1-1)=-22w-2+2w-1和-2w-1*-2w-1=-22w-2之間。要用補碼表示這個乘積可能需要2w位。W位的補碼乘法運算的結果為:
X*y = U2Tw((x*y)mod2w)
6. 乘以常數
大多數機器上,整數乘法指令相當慢,需要10個或者更多的時鐘周期,然而其他整型運算(加法、減法、位級運算和移位)隻需要1個時鐘周期。是以,編譯器使用了一項重要的優化,試着使用移位和加法運算的組合來替代乘以常數因子。如一個程式包含x*14
編譯器會将乘法重寫為(x<<3)+(x<<2)+(x<<1).
7. 除以2的幂
在大多數機器上,整數除法要比整數乘法更慢-需要30個或者更多地時鐘周期,除以2的幂也可以用移位運算來實作,隻不過用的是右移。無符号和補碼數分别使用邏輯移位和算術移位來達到目的。
小結
通過本篇我們了解了整數及其運算的規則,并從中看到了由于疏忽可能在程式設計中帶來的風險。最後我們以幾個常見的跟數值有關的邏輯判斷題結尾。
設有整型變量int x = val();
1> (x>0) || ((x-1)<0)false,當x等于TMin32(-2147483648)時,那麼x-1等于TMax32(2147483647)
2> x*x>=0false,當x=65535(0xffff)時,x*x=-131071(0xFFFE0001)
3> x<0||-x<=0true.對于TMin我們知道它的加法逆元就是它本身
4> x>0 ||-x>=0 false,當x等于Tmin(-2147483648).那麼x和-x都為負數
下一篇介紹浮點及其浮點運算的規則。
附錄
字,計算機系統中字的的概念是用來表示整數和指針資料的标稱大小。虛拟位址就是使用字來進行編碼的,也就是我們通常談論的32位機,64位機。
小端法—最低有效位元組存儲在最前面(即數值中的低位元組存儲在記憶體中的低位元組)
大端法—最高有效位元組存儲在最前面
(我們可以自己寫個簡單的程式檢視自己的系統是哪種表示法)
零擴充:當一個較小的數轉換為較大的數時,在較小數的位數前添加0
符号拓展:當一個較小的數轉換為較大的數時,根據較小數的最高位的值來添加。
加法逆元:對于一個數n,如果數m和其相加為0,那麼m就叫做n的加法逆元