很多博客上解释bitmap为位图，我认为这样的解释并不准确，我认为叫位映射比较好，因为它里面包含了映射关系，当然这里只是个人观点。早在x86的时代，就有寄存器存在位图，叫tss,可以自行百度，它的104偏移地址以上是位图，每个位对应一个IO端口，而提出这样的方案目的只有一个：高效。
bitmap其实是解决id的分配的，是一种高效率的分配。比如进程的pid的分配，还有文件描述符号的分配等。所以bitmap还是应用很广泛的，为了研究linux内核中的算法，我们提供了一种解决思路，帮助我们更好地理解内核，运用内核。话不多说，开始我们的主题。
在linux系统中运用的是内嵌汇编写的，它这样做是为了提高效率。我们的程序没那么复杂，关键是要理解它的思想。
这是一个简单的位图算法，先贴上代码，我们会对代码足以分析：
- #include <stdio.h>
- #include <unistd.h>
- #include <stdlib.h>
- int bitmap[10] = {0}; //0 - 320
- #define SHIFT 5
- #define MASK 0x1F
- void set_bit(int num){
- int index = num >> SHIFT;
- int bitValue = 1 << (num & MASK);
- bitmap[index] |= bitValue;
- }
- int text_set_bit(int num){
- int index = num >> SHIFT;
- int bitValue = 1 << (num & MASK);
- return bitmap[index] & bitValue;
- }
- void clear_bit(int num){
- int index = num >> SHIFT;
- int bitValue = 1 << (num & MASK);
- bitmap[index] &= (~bitValue);
- }
- int main(int argc, const char *argv[])
- {
- int num = 50;
- set_bit(num);
- printf("set_bit sucess\n");
- if(text_set_bit(num)){
- printf("match sucess! \n");
- }
- else{
- printf("match failed! \n");
- }
- clear_bit(num);
- printf("clear_bit sucess\n");
- if(text_set_bit(num)){
- printf("match sucess! \n");
- }
- else{
- printf("match failed! \n");
- }
- return 0;
- }
我们首先先理解一下位图分配的思想：这里有一个32位的二进制：1000 0110 , 它的思想是数二进制数字中置1的二进制的数目。比如： 1000 0110 为数字8，2， 1。（二进制0代表未分配，1代表已分配）。注意一下：这里并不是计算二进制的值，否则容易理解偏。
有了上面的理解，我们来分析一下怎么置位，我们看到上面用的是整形的数组。也就是每个元素是32位的，而且每个元素是连续的，正好满足上面二进制分配的规则。所以可以把这个数组想象成很长的二进制数，而里面为1的就是我们需要找到数字。
如何定义数组的下标和值，用简单的数学知识：
数组的下标为：index = num / 32;
数组的置位：value =1 <<( num % 32);（0 - 32 之间）
当然对于内核来说这样做浪费效率，所以为了提高效率，采取了移位操作，我们知道左移一个数字，相当于乘以这个数的2的幂次方，右移相反，所以就是int index = num >> SHIFT;大家能理解了。
我们重点理解：value =1 <<( num % 32);把这句话抽取出来，value = num % 32可以转化为(num & MASK); 这里可以做一个简单的计算，比如这个数字为34，十六进制0x22,二进制为：
0010 0010
& 0001 1111
0000 0010
答案显而易见为2，结果为这个数的第五位(由余数决定)，当然条件是：，a，余数必须为2的n次方 b，n为掩码的宽度。那我们为什么这样设计。可以理解一下，移动34位，与移动2位的效果是一样的。
因为这是由于数组的长度是固定的，而且占据32位。由此证明上面的结论是正确的。
而后我们只要数移动2位后为就是要设置的比特位。这里只用一个简单的技巧，就是左移这个数就行了。
bitmap[index] |= bitValue;后就是设置位，注意这里是或等于不是等于。设置好位后就能查询该位是否被使用。
下面是提供的api函数：
void set_bit(int num)； 根据数字设置相应的位
void clear_bit(int num)； 清除相应的位
int text_set_bit(int num)； 测试相应的位
你可以把上面的程序拷贝一下进行测试，还可以进行更高级的封装，为应用程序调用。
/2 
