上一篇:iOS標(biāo)準(zhǔn)庫中常用數(shù)據(jù)結(jié)構(gòu)和算法之KV數(shù)據(jù)庫
??位串
所謂位串就是由0和1組成的bit串，比如:010010110011101101101011?？梢园盐淮闯墒窃刂挥?和1組成的數(shù)組。一般情況下大量數(shù)據(jù)的標(biāo)志位采用位串進(jìn)行存儲(chǔ)這樣有利于存儲(chǔ)空間的節(jié)省，比如磁盤中分配的記錄塊的空閑標(biāo)志或者讀寫標(biāo)志等。位串的索引是從右往左從0開始計(jì)數(shù)。
功能:
系統(tǒng)提供了一套對位串進(jìn)行0，1設(shè)置和0，1判斷的函數(shù)，用于對位串進(jìn)行處理。系統(tǒng)提供的API函數(shù)都是以宏的形式提供的。
頭文件: #include <bitstring.h>
平臺(tái): BSD Unix
一、位串的創(chuàng)建
功能: 用于創(chuàng)建一個(gè)位串對象，你可以從堆內(nèi)存中創(chuàng)建也可以從棧內(nèi)存中創(chuàng)建，位串的數(shù)據(jù)類型是bitstr_t
函數(shù)簽名：
//從堆內(nèi)存中創(chuàng)建位串
bitstr_t * bit_alloc(int nbits);
//從棧內(nèi)存中聲明一個(gè)位串
bit_decl(bitstr_t *name, int nbits);
//返回某個(gè)長度的位串需要占用的字節(jié)數(shù)量。
int bitstr_size(int nbits);
參數(shù):
nbits: [in] 指定位串的長度。
name: [in] 主要用于棧內(nèi)存上分配位串，指定位串變量的名稱
return:[out] 函數(shù)返回一個(gè)位串對象的指針。
描述：
用于建立一個(gè)位串對象，系統(tǒng)提供兩種方法：堆內(nèi)存分配和棧內(nèi)存分配，堆內(nèi)存內(nèi)部通過calloc進(jìn)行分配，因此不使用時(shí)需要free掉，而棧內(nèi)存則不需要釋放處理。
示例代碼:
bitstr_t *p1 = bit_alloc(20); //從堆中分配20個(gè)長度的位串對象.
bitstr_t bit_decl(p2, 30); //從棧內(nèi)存中分配30個(gè)長度的位串對象.
//.....
free(p1);
二、位串的設(shè)置
功能:用于設(shè)置位串中某一位或者某一個(gè)區(qū)域的位的值，可設(shè)置的值只能為1或者0.
函數(shù)簽名:
//將指定位置或者指定區(qū)域的值設(shè)置為1
bit_set(bitstr_t *name, int bit);
bit_nset(bitstr_t *name, int start, int stop);
//將指定位置或者指定區(qū)域的值設(shè)置為0
bit_clear(bitstr_t *name, int bit);
bit_nclear(bitstr_t *name, int start, int stop);
參數(shù):
name:[in] 位串變量
bit、start、stop:[in] 位串的位置索引
描述:
用于將位串中指定位置的值設(shè)置為1或者0，位串的索引位置是從0開始的，并且是從右往左進(jìn)行遞增的，注意的是這個(gè)索引位置不能超過位串的長度。
三、位串的測試
功能：用來判斷位串中某個(gè)位置的值是0還是1。
函數(shù)簽名:
//判斷位串中的第bit位的值是0還是1
int bit_test(bitstr_t *name, int bit);
//判斷位串中第一個(gè)被設(shè)置為0的位置索引
bit_ffc(bitstr_t *name, int nbits, int *value);
//判斷位串中第一個(gè)被設(shè)置為1的位置索引
bit_ffs(bitstr_t *name, int nbits, int *value);
參數(shù)：
name:[in] 位串對象。
bit:[in] 位串的索引位置
nbits:[in] 位串的長度。
value:[out] 一個(gè)位置指針，輸出位串的特定值的位置。
return:[out] 用于bit_test函數(shù)，返回測試的結(jié)果。
描述:
bit_ffc函數(shù)和bit_ffs函數(shù)用來獲取某個(gè)位串長度下從右往左的順序中第一個(gè)為0或者第一個(gè)為1的值的索引位置。如果整個(gè)串都是1那么bit_ffc函數(shù)的返回值將是-1， 如果整個(gè)串都是0那么bit_ffs的返回值將是-1.
示例代碼:
bitstr_t *p = bit_alloc(10); //0000000000
//位串設(shè)置
bit_set(p, 2); //0000000100
bit_nset(p, 7,8); //0110000100
bit_clear(p, 8); //0010000100
//位串測試
int ret = bit_test(p, 2); //ret == true
ret = bit_test(p,3); //ret == false
//位串測試2
int v1,v2;
bit_ffc(p, 10, &v1); //v1 == 0, 第一個(gè)為0的位置是第0位
bit_ffs(p, 10, &v2); //v2 == 2 第一個(gè)為1的位置是第2位。
free(p);
四、整數(shù)中的位標(biāo)志讀取
功能：獲取整數(shù)中的第一個(gè)和最后一個(gè)比特值為1的位置。
頭文件: #include <strings.h>
平臺(tái)： POSIX
函數(shù)簽名:
//獲取整數(shù)中從右往左開始的第一個(gè)比特值為1的位置。
int ffs(int value);
int ffsl(long value);
int ffsll(long long value);
//獲取整數(shù)中從右往左開始的最后一個(gè)比特值為1的位置。
int fls(int value);
int flsl(long value);
int flsll(long long value);
描述：
- 因?yàn)檎麛?shù)可以看成是一個(gè)具有固定長度的位串，因此針對整數(shù)系統(tǒng)提供了上述的函數(shù)。上述函數(shù)返回的是比特值1所在的位置，并且是從1開始計(jì)數(shù)的，如果返回0則表明這個(gè)整數(shù)值就是0。
- ffs系列函數(shù)返回的是第一個(gè)比特位為1的位置。因此這個(gè)函數(shù)可以用來獲取整數(shù)的比特對齊的位數(shù)。
- fls系列函數(shù)返回的是最后一個(gè)比特位為1的位置。
示例代碼：
int a = 5; //00000000000000000000000000000101
int idx = ffs(a); //idx == 1
idx = fls(a); //idx == 3
idx = ffs(0); // idx == 0
idx = fls(0); // idx == 0
五、整數(shù)中的位個(gè)數(shù)計(jì)數(shù)
功能：獲取一個(gè)整數(shù)中0或者1bit位的數(shù)量。
函數(shù)簽名：
//返回從左邊數(shù)起(高位)0的個(gè)數(shù)
int __builtin_clz (unsigned int x)
int __builtin_clzl (unsigned long x)
//返回從右邊數(shù)起(低位)0的個(gè)數(shù)
int __builtin_ctz (unsigned int x)
int __builtin_ctzl (unsigned long x)
//返回bit值為1的數(shù)量
int __builtin_popcount (unsigned int x)
int __builtin_popcountl (unsigned long x)
描述：
這6個(gè)函數(shù)是編譯器內(nèi)聯(lián)的函數(shù)，用來獲取一個(gè)整數(shù)中的特定的比特位的個(gè)數(shù)。
示例代碼:
//10的二進(jìn)制值為：00000000000000000000000000001010
int a = __builtin_clz(10); //a == 28
a = __builtin_ctz(10); // a == 1
a = __builtin_popcount(10); //a == 2
下一篇：iOS標(biāo)準(zhǔn)庫中常用數(shù)據(jù)結(jié)構(gòu)和算法之內(nèi)存池
