計(jì)算機(jī)中信息的表示與處理

信息的編碼方式
在計(jì)算機(jī)中信息都是以0、1兩種數(shù)據(jù)來表示的，大家都知道，但是就是這兩個(gè)簡單的0、1如何實(shí)現(xiàn)了計(jì)算機(jī)的強(qiáng)大計(jì)算呢？這就涉及到了計(jì)算機(jī)中信息的表達(dá)和處理。在大學(xué)計(jì)算基礎(chǔ)課上，開始就涉及了二進(jìn)制、八進(jìn)制、十進(jìn)制、十六進(jìn)制等進(jìn)制之間的轉(zhuǎn)換方式。其中二進(jìn)制是計(jì)算機(jī)的實(shí)現(xiàn)方式，其他的進(jìn)制都是出于一些目的定義的。在二進(jìn)制中有三個(gè)基礎(chǔ)概念：原碼、反碼、補(bǔ)碼是非常重要的，很多人也對三者之間的轉(zhuǎn)換方式非常清楚。
原碼：對于十進(jìn)制的數(shù)據(jù)，可以采用多個(gè)0、1構(gòu)成的比特向量表示，其中最高位表示符號位，當(dāng)為1時(shí)，表示這個(gè)數(shù)為負(fù)數(shù)，當(dāng)為0時(shí)，表示這個(gè)數(shù)為正數(shù)。
反碼：是指原碼符號位除外的其他位進(jìn)行取反操作，但是取反操作只針對負(fù)數(shù)，也就是說正數(shù)的原碼等于反碼。
補(bǔ)碼：也只是針對負(fù)數(shù)而言，對于負(fù)數(shù)補(bǔ)碼是指在反碼的基礎(chǔ)上加1即表示補(bǔ)碼（但是不能改變符號位數(shù)據(jù)）。對于正數(shù)而言，補(bǔ)碼等于反碼，等于原碼。
我們可以這樣認(rèn)為，為了解決負(fù)數(shù)的問題，在計(jì)算機(jī)中引入了反碼、補(bǔ)碼的概念，且補(bǔ)碼、反碼主要針對的對象就是負(fù)數(shù)，正數(shù)的補(bǔ)碼、原碼、反碼是相同的bit向量。

在實(shí)際運(yùn)用中補(bǔ)碼相比另外兩種編碼方式更加的方便，因此對于有符號整形類型，幾乎所有的編譯器中都是采用補(bǔ)碼方式進(jìn)行編碼，了解到編譯器是采用補(bǔ)碼的形式存儲(chǔ)計(jì)算機(jī)的整形數(shù)據(jù)信息是非常重要的。

一般而言，對于有符號的整數(shù)型數(shù)據(jù)類型，即char、short、int這種類數(shù)據(jù)類型，都是采用補(bǔ)碼方式編碼的，但是對于無符號的整數(shù)型數(shù)據(jù)類型，一般都是采用原碼的形式編碼的，也就是單純的比特向量，沒有符號位之說，由于常用的計(jì)算機(jī)系統(tǒng)都是32bit，這也是為什么說計(jì)算機(jī)的地址空間是4G=2^32字節(jié)。char型數(shù)據(jù)類型占1字節(jié)的空間，而short類型一般占用2字節(jié)的空間，int型數(shù)據(jù)占用4個(gè)字節(jié)的空間。32個(gè)bit剛好占有4字節(jié)，因此我們可以認(rèn)為int數(shù)據(jù)實(shí)際上就是一個(gè)32個(gè)bit向量。

由實(shí)際情況可知：
int型的范圍是-2^31---2^31-1,可以認(rèn)為是非對稱的空間。無符號的unsigned int的范圍則是0到2^32-1之間。
char型的范圍是-128到-127之間，unsigned char的范圍則是0到255之間，在很多的應(yīng)用中可以充分運(yùn)用char的范圍減小存儲(chǔ)量。
short的范圍是-2^15到2^15-1,unsigned short 的范圍是0-2^16-1。
需要了解的是有符號的整數(shù)型數(shù)據(jù)都是采用補(bǔ)碼方式進(jìn)行編碼的，而無符號的數(shù)據(jù)類型一般采用原碼方式編碼（正數(shù)）。兩種編碼方式表示數(shù)據(jù)的范圍存在差別，實(shí)際上在C語言編程的過程中都會(huì)進(jìn)行隱式的強(qiáng)制類型轉(zhuǎn)換，如果不清楚編碼方式的差別，就很難準(zhǔn)確的把握計(jì)算的差別。在嵌入式編程中經(jīng)常會(huì)有一些簡單的延遲操作，如果編寫不恰當(dāng)就會(huì)導(dǎo)致錯(cuò)誤產(chǎn)生。如下所示：

void delay(int time)
{
unsigned char i = 0;
for(; time >= 0; -- time)
for(i = 0; i < 256; ++ i)
；
}

這個(gè)題乍一看沒什么問題，但是仔細(xì)推敲就會(huì)發(fā)現(xiàn)存在問題，因?yàn)榇嬖谒姥h(huán)，unsigned char的最大值是255，不可能大于等于256，因此一直滿足條件，也就是說第二個(gè)循環(huán)會(huì)一直執(zhí)行，這就是典型的不注意范圍問題。
還有一個(gè)典型的排序問題：

unsigned char array[1000][1000];

void sort(unsigned char (*a)[1000])
{}

這種屬于典型的大數(shù)排序問題，只有選擇合適的排序策略才能減少排序的時(shí)間復(fù)雜度，那么如何實(shí)現(xiàn)呢？最簡單的方式是采用計(jì)數(shù)排序，時(shí)間復(fù)雜度為O(n)。充分利用了unsigned char的數(shù)值范圍在0-255之間這個(gè)范圍。
左移右移處理
在整形數(shù)據(jù)類型中有一個(gè)問題就是典型的移位操作，在機(jī)器語言中也會(huì)有位操作，在C語言中也存在位操作，這為直接控制CPU提供了較好的實(shí)現(xiàn)方式。移位主要包含左移和右移操作，其中左移的實(shí)現(xiàn)是在當(dāng)前數(shù)據(jù)的bit向量向左移動(dòng)n個(gè)bit，后續(xù)的bit補(bǔ)0。
而右移比左移復(fù)雜一些，右移存在兩種：邏輯右移和算術(shù)右移，邏輯右移主要是針對無符號型數(shù)據(jù)，邏輯右移是指將當(dāng)前的bit向量向右移動(dòng)，左邊bits補(bǔ)零。算術(shù)右移主要針對有符號型數(shù)據(jù)，將當(dāng)前數(shù)據(jù)右移，左邊補(bǔ)上最高bit的值。這種實(shí)現(xiàn)方式能夠保證數(shù)據(jù)的符號不改變，也就是說負(fù)數(shù)通過右移以后還是負(fù)數(shù)，不會(huì)變成正數(shù)。而邏輯右移則不行，負(fù)數(shù)通過邏輯右移以后就變成了正數(shù)，這是不合理的。因此可以總結(jié)如下：

對于左移操作，不管是有符號還是無符號類型，都是右端直接補(bǔ)零。這時(shí)候可能導(dǎo)致數(shù)據(jù)發(fā)生較大的變化，正數(shù)通過左移變成了負(fù)數(shù)，出現(xiàn)這些的原因?qū)嶋H上是左移操作忽略了進(jìn)位操作，正負(fù)都是合理的。在整形數(shù)據(jù)中經(jīng)常采用左移操作實(shí)現(xiàn)數(shù)據(jù)的乘法操作，兩個(gè)正數(shù)相乘是有可能產(chǎn)生負(fù)數(shù)的。比如：

int x1 = 0x60000000;
printf("%d,%d,%d",x1,x1<<1,x1*2);

這段代碼就說明了兩個(gè)正數(shù)相乘是可以產(chǎn)生一個(gè)負(fù)數(shù)的，但是如果我們采用無符號數(shù)據(jù)類型進(jìn)行左移操作就不會(huì)產(chǎn)生兩個(gè)正數(shù)相乘產(chǎn)生負(fù)數(shù)的情況，這樣能夠避免很多不可思議的結(jié)果。
右移操作中的邏輯右移主要是針對無符號數(shù)據(jù)類型，對有符號的數(shù)據(jù)類型是無效的，對于有符號的數(shù)據(jù)類型，右移操作對于大多數(shù)的編譯器都認(rèn)為是算術(shù)右移，算術(shù)右移能夠保證數(shù)據(jù)的正負(fù)特性，不會(huì)發(fā)生左移中兩個(gè)正數(shù)相乘得到負(fù)值的情況。算術(shù)右移的實(shí)質(zhì)是在移位操作以后，數(shù)據(jù)的左邊采用符號位填充。通常在C語言中右移實(shí)現(xiàn)除法操作，比如8>>1,即實(shí)現(xiàn)了除以2的操作，對于無符號型數(shù)據(jù)可以采用右移操作實(shí)現(xiàn)除法操作，但是對于有符號數(shù)據(jù)類型可能出現(xiàn)錯(cuò)誤。下面說一個(gè)典型的例子：

int x1 = -1;
printf("%d,%d,%d",x1,x1>>1,x1/2);

這個(gè)例子說明了有符號數(shù)據(jù)類型通過算術(shù)右移并不能完成除法操作，但是無符號的數(shù)據(jù)類型基本上可以完成除法操作。搞清楚何時(shí)是算術(shù)右移何時(shí)是邏輯右移是非常有必要的。
對于無符號數(shù)據(jù)類型，采用左移右移的方式提高乘除法的速度是可行的，但是對有符號的數(shù)據(jù)類型最好不要采用這種實(shí)現(xiàn)方式，因?yàn)榭赡軙?huì)出現(xiàn)意想不到的結(jié)果。雖然很多的程序書中建議少用unsigned的類型，但是在移位操作這方面最好還是處理無符號型對象比較有保證。

強(qiáng)制類型轉(zhuǎn)換處理
強(qiáng)制類型轉(zhuǎn)換是C語言中比較重要的一個(gè)主題，其中程序員老手也會(huì)忽略這種問題的發(fā)生，基本的實(shí)現(xiàn)方式是有符號向無符號轉(zhuǎn)變，小字節(jié)數(shù)據(jù)朝大字節(jié)數(shù)據(jù)轉(zhuǎn)換，當(dāng)然也有高字節(jié)數(shù)據(jù)類型往低字節(jié)數(shù)據(jù)轉(zhuǎn)變的問題。
基本的轉(zhuǎn)換存在兩種：零擴(kuò)展和符號擴(kuò)展。
零擴(kuò)展是針對無符號數(shù)據(jù)類型，將一個(gè)小字節(jié)數(shù)據(jù)轉(zhuǎn)換為大字節(jié)數(shù)據(jù)時(shí)，在高字節(jié)中填充零，實(shí)現(xiàn)數(shù)據(jù)的一致型。
符號擴(kuò)展則針對有符號數(shù)據(jù)類型，將一個(gè)小字節(jié)數(shù)據(jù)轉(zhuǎn)換為大字節(jié)數(shù)據(jù)時(shí)，在高字節(jié)中填充小字節(jié)數(shù)據(jù)的符號位，填充符號位主要是為了實(shí)現(xiàn)補(bǔ)碼一致原則。零擴(kuò)展實(shí)際上是符號擴(kuò)展的子類。
大字節(jié)數(shù)據(jù)向小字節(jié)數(shù)據(jù)轉(zhuǎn)換的過程是一個(gè)截取過程，這樣可能會(huì)導(dǎo)致數(shù)據(jù)正負(fù)的變化，也就是說大到小的過程可能發(fā)現(xiàn)比較大的變化，截取數(shù)據(jù)的一部分作為小字節(jié)數(shù)據(jù)的bit向量。
強(qiáng)制類型轉(zhuǎn)換實(shí)質(zhì)上包含了符號擴(kuò)展，和零擴(kuò)展，符號擴(kuò)展保證了補(bǔ)碼的一致型，零擴(kuò)展則保證了數(shù)值大小的一致性，符號擴(kuò)展針對有符號數(shù)據(jù)類型，而零擴(kuò)展主要針對無符號數(shù)據(jù)類型。
很多時(shí)候的強(qiáng)制類型轉(zhuǎn)換是隱含進(jìn)行的，這是就需要我們準(zhǔn)確的把握，有符號類型到無符號類型的轉(zhuǎn)變會(huì)導(dǎo)致很大的差別，因?yàn)闊o符號類型數(shù)加上有符號類型數(shù)將進(jìn)行有符號到無符號數(shù)據(jù)類型的轉(zhuǎn)換，這時(shí)候就會(huì)產(chǎn)生一個(gè)無符號的數(shù)據(jù)，不會(huì)產(chǎn)生有符號類型的數(shù)。
同時(shí)還有一個(gè)技巧，在C語言中如何判斷兩個(gè)數(shù)的和是否越界的問題，由于很多編譯器對越界并不報(bào)錯(cuò)，這時(shí)候可以通過判斷兩個(gè)數(shù)的和是否小于任何一個(gè)數(shù)即可，如果小于任何一個(gè)，則說明這個(gè)數(shù)就是越界，否則沒有發(fā)生越界問題。
具體的實(shí)現(xiàn)可以采用下面的代碼測試：

int test()
{
char x2 = -20;
int x1 = x2;
printf("x2 = %d, x1 = %u",x2,x1);
x2 = 20;
x1 = x2;
printf("x2 = %d, x1 = %u",x2,x1);
}

浮點(diǎn)型數(shù)據(jù)類型
浮點(diǎn)型數(shù)據(jù)類型在前一章中已經(jīng)說明了，浮點(diǎn)型數(shù)據(jù)類型沒有無符號和有符號之說。浮點(diǎn)型具有固定的編碼方式，本來就是存在正負(fù)之分，即沒有unsigned float之說。需要注意的是浮點(diǎn)型是一個(gè)近似的值不能用來比較。還有對float類型數(shù)據(jù)不能進(jìn)行移位操作，因?yàn)閒loat是有固定的編碼方式的不像整形數(shù)據(jù)。

總結(jié)
了解計(jì)算機(jī)中的有符號整型數(shù)據(jù)一般按照補(bǔ)碼的方式存在，有符號數(shù)據(jù)類型的擴(kuò)展是按照符號擴(kuò)展，而不是簡單的零擴(kuò)展，符號擴(kuò)展是零擴(kuò)展的延伸，主要是保證在延伸的過程中符號、數(shù)值保持不變。
在移位操作過程中，有符號、無符號數(shù)據(jù)類型的左移都沒有問題，但是可能會(huì)導(dǎo)致數(shù)據(jù)類型的改變，特別是有符號數(shù)據(jù)類型。對于對于右移操作需要注意，有符號數(shù)據(jù)類型是算術(shù)右移，而無符號數(shù)據(jù)類型是邏輯右移，右移的差別是在左端補(bǔ)齊的值的差別。
在用移位來模擬數(shù)據(jù)的乘除法時(shí)特別要注意，對無符號數(shù)據(jù)類型是最有效的，左移右移的值也是我們認(rèn)為正確的值，但是如果是對有符號數(shù)據(jù)類型進(jìn)行右移模擬除法過程，左移模擬乘法過程時(shí)可能導(dǎo)致結(jié)果不是所想。因此建議只對無符號數(shù)據(jù)類型采用移位來簡化乘除操作。