iOS标准库中常用数据结构和算法之位串
?位串
所谓位串就是由0和1组成的bit串，比如:010010110011101101101011。可以把位串看成是元素只有0和1组成的数组。一般情况下大量数据的标志位采用位串进行存储这样有利于存储空间的节省，比如磁盘中分配的记录块的空闲标志或者读写标志等。位串的索引是从右往左从0开始计数。
功能: 系统提供了一套对位串进行0，1设置和0，1判断的函数，用于对位串进行处理。系统提供的API函数都是以宏的形式提供的。 头文件: #include <bitstring.h> 平台: BSD Unix
1.位串的创建
功能: 用于创建一个位串对象，你可以从堆内存中创建也可以从栈内存中创建，位串的数据类型是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);2.位串的设置
功能:用于设置位串中某一位或者某一个区域的位的值，可设置的值只能为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开始的，并且是从右往左进行递增的，注意的是这个索引位置不能超过位串的长度。
3.位串的测试
功能：用来判断位串中某个位置的值是0还是1。 函数签名:
//判断位串中的第bit位的值是0还是1
int bit_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);