iOS標準庫中常用資料結構和演算法之位串
所謂位串就是由0和1組成的bit串，比如:010010110011101101101011
。可以把位串看成是元素只有0和1組成的陣列。一般情況下大量資料的標誌位採用位串進行儲存這樣有利於儲存空間的節省，比如磁碟中分配的記錄塊的空閒標誌或者讀寫標誌等。位串的索引是從右往左從0開始計數。
功能: 系統提供了一套對位串進行0，1設定和0，1判斷的函式，用於對位串進行處理。系統提供的API函式都是以巨集的形式提供的。
標頭檔案: #include <bitstring.h>
平臺: BSD Unix
一、位串的建立
功能: 用於建立一個位串物件，你可以從堆記憶體中建立也可以從棧記憶體中建立，位串的資料型別是bitstr_t
函式簽名：
//從堆記憶體中建立位串 bitstr_t * bit_alloc(int nbits); //從棧記憶體中宣告一個位串 bit_decl(bitstr_t *name, int nbits); //返回某個長度的位串需要佔用的位元組數量。 int bitstr_size(int nbits); 複製程式碼
引數:
nbits: [in] 指定位串的長度。
name: [in] 主要用於棧記憶體上分配位串，指定位串變數的名稱
return:[out] 函式返回一個位串物件的指標。
描述：
用於建立一個位串物件，系統提供兩種方法：堆記憶體分配和棧記憶體分配，堆記憶體內部通過calloc進行分配，因此不使用時需要free掉，而棧記憶體則不需要釋放處理。
示例程式碼:
bitstr_t *p1 = bit_alloc(20);//從堆中分配20個長度的位串物件. bitstr_t bit_decl(p2, 30);//從棧記憶體中分配30個長度的位串物件. //..... free(p1); 複製程式碼
二、位串的設定
功能:用於設定位串中某一位或者某一個區域的位的值，可設定的值只能為1或者0.
函式簽名:
//將指定位置或者指定區域的值設定為1 bit_set(bitstr_t *name, int bit); bit_nset(bitstr_t *name, int start, int stop); //將指定位置或者指定區域的值設定為0 bit_clear(bitstr_t *name, int bit); bit_nclear(bitstr_t *name, int start, int stop); 複製程式碼
引數:
name:[in] 位串變數
bit、start、stop:[in]位串的位置索引
描述:
用於將位串中指定位置的值設定為1或者0，位串的索引位置是從0開始的，並且是從右往左進行遞增的，注意的是這個索引位置不能超過位串的長度。
三、位串的測試
功能：用來判斷位串中某個位置的值是0還是1。
函式簽名:
//判斷位串中的第bit位的值是0還是1 intbit_test(bitstr_t *name, int bit); //判斷位串中第一個被設定為0的位置索引 bit_ffc(bitstr_t *name, int nbits, int *value); //判斷位串中第一個被設定為1的位置索引 bit_ffs(bitstr_t *name, int nbits, int *value); 複製程式碼
引數：
name:[in] 位串物件。
bit:[in] 位串的索引位置
nbits:[in] 位串的長度。
value:[out] 一個位置指標，輸出位串的特定值的位置。
return:[out] 用於bit_test函式，返回測試的結果。
描述:
bit_ffc函式和bit_ffs函式用來獲取某個位串長度下從右往左的順序中第一個為0或者第一個為1的值的索引位置。如果整個串都是1那麼bit_ffc函式的返回值將是-1， 如果整個串都是0那麼bit_ffs的返回值將是-1.
示例程式碼:
bitstr_t *p = bit_alloc(10);//0000000000 //位串設定 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,第一個為0的位置是第0位 bit_ffs(p, 10, &v2);//v2 == 2第一個為1的位置是第2位。 free(p); 複製程式碼
四、整數中的位標誌讀取
功能：獲取整數中的第一個和最後一個位元值為1的位置。
標頭檔案: #include <strings.h>
平臺： POSIX
函式簽名:
//獲取整數中從右往左開始的第一個位元值為1的位置。 int ffs(int value); int ffsl(long value); int ffsll(long long value); //獲取整數中從右往左開始的最後一個位元值為1的位置。 int fls(int value); int flsl(long value); int flsll(long long value); 複製程式碼
描述：
- 因為整數可以看成是一個具有固定長度的位串，因此針對整數系統提供了上述的函式。上述函式返回的是位元值1所在的位置，並且是從1開始計數的，如果返回0則表明這個整數值就是0。
- ffs系列函式返回的是第一個位元位為1的位置。因此這個函式可以用來獲取整數的位元對齊的位數。
- fls系列函式返回的是最後一個位元位為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 複製程式碼
五、整數中的位個數計數
功能：獲取一個整數中0或者1bit位的數量。
函式簽名：
//返回從左邊數起(高位)0的個數 int __builtin_clz (unsigned int x) int __builtin_clzl (unsigned long x) //返回從右邊數起(低位)0的個數 int __builtin_ctz (unsigned int x) int __builtin_ctzl (unsigned long x) //返回bit值為1的數量 int __builtin_popcount (unsigned int x) int __builtin_popcountl (unsigned long x) 複製程式碼
描述：
這6個函式是編譯器內聯的函式，用來獲取一個整數中的特定的位元位的個數。
示例程式碼:
//10的二進位制值為：00000000000000000000000000001010 int a = __builtin_clz(10);//a == 28 a = __builtin_ctz(10);// a == 1 a = __builtin_popcount(10);//a == 2 複製程式碼