本文關(guān)鍵詞：編程珠璣，由筆耕文化傳播整理發(fā)布。

第一章

以下轉(zhuǎn)載自 

位向量的定義和應(yīng)用：位向量/位圖在充分利用小空間存儲(chǔ)大數(shù)據(jù)方面很有優(yōu)勢(shì)。Linux內(nèi)核中很多用到了位向量。

一般地，對(duì)于多個(gè)對(duì)象和一個(gè)性質(zhì)，這些對(duì)象可能滿(mǎn)足(true)也可能不滿(mǎn)足(false)這條性質(zhì)。那么，為了表示所有對(duì)象對(duì)這個(gè)性質(zhì)的滿(mǎn)足情況，最容易想到的方式是分配一個(gè)int型變量（這里不討論布爾型，C++沒(méi)有對(duì)布爾型占用空間有明確規(guī)定；本文主要討論C）作為標(biāo)志，用1表示滿(mǎn)足條件，用0表示不滿(mǎn)足條件。同時(shí)為了方便查詢(xún)，把這些對(duì)象的標(biāo)志整合成一個(gè)數(shù)組。顯然，使用int來(lái)表示是0還是1有些太浪費(fèi)空間了，即使把int改為char，浪費(fèi)的情況也只是減輕了一部分，仍有很大的空間被浪費(fèi)。考慮到計(jì)算機(jī)中最小的數(shù)據(jù)單位是非0即1的二進(jìn)制位，對(duì)于一個(gè)對(duì)象，使用一個(gè)二進(jìn)制位就足夠了。很多語(yǔ)言都具有位運(yùn)算，利用位運(yùn)算是可以完成本段開(kāi)始處提出的要求的。當(dāng)然，因?yàn)椴荒苡靡粋�(gè)變量名直接表示一個(gè)位，那么可以將多個(gè)位組合成一個(gè)基本數(shù)據(jù)類(lèi)型，通過(guò)對(duì)這個(gè)基本數(shù)據(jù)類(lèi)型進(jìn)行操作，達(dá)到使用位的方法。同時(shí)，為了方便，延續(xù)使用int數(shù)組的做法，把這些由位組合成的基本數(shù)據(jù)類(lèi)型也組成數(shù)組。

經(jīng)過(guò)這樣分析，位向量的實(shí)現(xiàn)方法大體是：多個(gè)位組成一個(gè)基本數(shù)據(jù)類(lèi)型，基本數(shù)據(jù)類(lèi)型組合成數(shù)組。根據(jù)這個(gè)思路就可以寫(xiě)出位向量的表示了。在閱讀下面代碼前，建議讀者嘗試自己獨(dú)立完成，這是一些提示：簡(jiǎn)單起見(jiàn)，使用int作為位組成的基本數(shù)據(jù)類(lèi)型，且int使用32位表示；int數(shù)組中元素的個(gè)數(shù)如何計(jì)算？

#define N 10000000 //number of elements #define BITPERWORD 32 //bits of int depends on machine int a[(N-1)/BITPERWORD + 1]; //allocate space for bitmap //《編程珠璣》原書(shū)中是N/BITPERWORD + 1 //如果N恰為BITPERWORD的倍數(shù)，那么又要浪費(fèi)一個(gè)int的空間了 //N取0時(shí)，仍會(huì)浪費(fèi)一個(gè)int的空間 //N非0非BITPERWORD的倍數(shù)時(shí)，最多是最后一個(gè)int不完全利用而已

寫(xiě)完了表示，，就需要為這個(gè)數(shù)據(jù)結(jié)構(gòu)增加對(duì)應(yīng)的操作了。對(duì)于每個(gè)位的操作，有三種：設(shè)置為0、設(shè)置為1、讀取當(dāng)前值。根據(jù)上文位向量的表示，實(shí)現(xiàn)這三種操作。同樣建議讀者先嘗試獨(dú)立完成。以下代碼參考自《編程珠璣》習(xí)題1.2。 #define SHIFT 5 //32 = 2^5 #define MASK 0x1F // vaule 11111 in binary //i代表需要進(jìn)行操作的第i個(gè)對(duì)象 //i>>SHIFT相當(dāng)于i/32，將i定位到具體是哪個(gè)int中，即a[i>>SHIFT] //i&MASK相當(dāng)于i%32 只保留i的0至4位，即i在int中的第幾位，然后把1左移這么多位 //將a[i>>SHIFT]和(1<<(i&MASK))視需要進(jìn)行操作 //同1做或運(yùn)算或即為位設(shè)置 //同1取反再做與運(yùn)算即為位清除 //同1做與，結(jié)果為0則原位為0，為1則原位為1 void set(int i) { a[i>>SHIFT] |= (1<<(i&MASK));} void clr(int i) { a[i>>SHIFT] &= ~(1<<(i&MASK));} void test(int i) { return a[i>>SHIFT] & (1<<(i&MASK));} 使用位向量前不要忘記對(duì)所有位進(jìn)行初始化：for(i=0;i<N;i++) clr(i);Q：為什么不用看上去比較直接的i / 32或者i % 32？

A：提高效率

  本文關(guān)鍵詞：編程珠璣，由筆耕文化傳播整理發(fā)布。

本文編號(hào)：330781