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
  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);

复制代码

四、整数中的位标志读取

功能：获取整数中的第一个和最后一个比特值为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所在的位置，并且是从1开始计数的，如果返回0则表明这个整数值就是0。
2. ffs系列函数返回的是第一个比特位为1的位置。因此这个函数可以用来获取整数的比特对齐的位数。
3. 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
复制代码