位图是一种非常有用的数据结构，对于处理系统中的进程数管理、磁盘中的磁盘块管理和内存中内存页面的使用情况管理非常有用。
同时在内核中对位图进行各种操作，总结现在常用的操作，便于以后使用时回顾。
一些常见的宏定义：
#define BIT_PER_TYPE 8
#define __WORDSIZE 32
#define BITS_PER_LONG __WORDSIZE
#definediv_round_up(NR，d ) () ) ) )。
(nr ) (d )- 1 )/(d ) ) ) )。
此DIV_ROUND_UP(nr， d]宏的作用是，如果将unsinged long name[128]用作位图，则d=32bits，假定nr=128*32 - 1，数组中的n的下标可以通过NR 所有DIV_ROUND_UP )函数的作用都可以通过将比特与数组的大小相关联来根据nr比特确定数组的长度。
#definebits_to_longs(bits ) div_round_up ) bits，sizeof (long ) * BTT_PER_BYTE () ) ) ) )
#definedefine_bitmap(name，bits ) () )。
unsigendlongintname [ bits _ to _ longs (bits ) ]
dfine_bitmap(name，bits )定义位图，name是位图的名称，bits是位图的大小。
#定义位(nr ) 1ul ) nr )/1向左移动nr位
#definebit_mask(nr ) 1ul ) ) nr ) % BITS_PER_LONG ) /第nr位置1；
#definebit_word(NR ) ) nr/BITS_PER_LONG )/NR在其数组元素中；
# definebitmap _ last _ word _ mask (bits ) )
(bits % BITS_PER_LONG )？ (1)1 (bits % BITS_PER_LONG ) (- 1 : ~0UL
BITMAP_LAST_WORD_MASK ) )主要用于存储具有第bits位的元素的第一个(bits % BITS_PER_LONG -1 )位的值。
2 .位图中的函数操作：
1 .判断位图是否尚未使用：
//bitmap :位图的起始地址；
//bits :位图的大小
int _ _ bitmap _ empty (统一长*位图，int bits ) )。
{
无符号长* addr=bitmap；
未指定int k，limit；
limit=bits/BITS_PER_LONG； //数组下标值；
为了查看//数组下标为0 - limit-1的所有数组元素是否都为0
for(k=0； 克丽美特； k )
{
if(addr[k] ) )。
返回0；
}
//看下标为bits/BITS_PER_LONG的元素的0 - bits%BITS_PER_LONG-1位是否也全部为零
if(bits%bits_per_long ) )。
{
if (addr [ k ] bitmap _ last _ word _ mask (bits ) )
返回0；
}
返回1；
}
如果位图中的所有位都为0，则int __bitmap_empty )返回1。 否则还0；
2 .确定一个位图中的所有位是否都设置为1 :
int _ _ bitmap _ full (未指定长* bitmap，int bits ) )。
{
无符号长* addr=bitmap；
int k，limit；
limit=bits/BITS_PER_LONG；
for(k=0； 克丽美特； k )
{
//如果~addr[k]的各位为1，则~addr[k]必然为0；
//否则，如果addr[k]中的比特为1，而某个比特为0，则~addr[k]的各个比特也一定为零，某个比特为1。
(if(addr[k] ) ) ) ) ) ) ) ) ) ) ) )。
返回0；
}
if (位%位
S_PER_LONG){
if( ~addr[k] & BITMAP_LAST_WORD_MASK(bits) )
return 0;
}
return 1;
}
3.判断两个位图是否相等，前提时这两个位图的长度必须要相等。
int __bitmap_equal(unsigned long *bitmap1, unsigned long *bitmap2, int bits)
{
int k , limit;
limit = bits / BITS_PER_LONG;
for(k = 0; k < limit; k++)
{
// ^ 是异或操作运算符， 如果 a == b 则 a ^ b == 0
如果 a != b 则 a ^ b != 0
// 所以判断两个数是否相等，可以将这两个数进行异或操作，结果为0，表示相等
结果不为0，表示不想等
if(bitmap1[k] ^ bitmap[k])
return 0;
}
if(bits % BITS_PER_LONG)
{
if( (bitmap1[k] ^ bitmap[k]) & BITMAP_LAST_WORD_MASK(bits) )
return 0;
}
return 1;
}
4. 对一个位图中的所有位进行取反操作，然后将结果存入到另一个位图中：
void __bitmap_complement(unsigned long *dest, unsigned long *src, int bits)
{
int k, limit;
limit = bits / BITS_PER_LONG ;
for(k = 0 ; k < limit ; k++)
dest[k] = ~src[k];
if(bits % BITS_PER_LONG )
dest[k] = ~src[k] & BITMAP_LAST_WORD_MASK(bits);
}
5.判断一个位图是否是另一个位图的子集：
此处用到的数学集合的思想： 如果 A 属于 B 话，即A 是 B 的子集的，那么 A 必然不属于 ～B了； A & ～B其结果必然为0；
int __bitmap_subset(unsigned long *bitamp1, unsigned long *bitmap2, int bits)
{
int k, limit;
limit = bits / BITS_PER_LONG ;
for(k = 0; k < limit ; k++)
{
// 用于bitmap1[]中的每个元素的二进制形式是否是bitmap2[]中的每个元素二进制的
//子集。如果是的话，则 bitmap1[k] & ～bitmap2[k]为零；否则非零。
if(bitmap1[k] & ~bitmap2[k])
return 0;
}
if(bits % BITS_PER_LONG)
if((bitmap1[k] & ~bitmap2[k]) & BITMAP_LAST_WORD_MASK(bits) )
return 0;
return 1;
}
6.用于求出位图中已经置为1的位的个数：
int __bitmap_weight(unsigned long *bitmap, int bits)
{
int count, k, limit;
count = 0;
limit = bits / BITS_PER_LONG ;
for(k = 0; k < limit ; k++)
count += hweight_long(bitmap[k]);
if( bits % BITS_PER_LONG )
count += hweight_long(bitmap[k] & BITMAP_LAST_WORD_MASK(bits))
return count;
}
hweight_long() 用于计算一个8,16,32位的二进制数，1的个数；
下面的这几个函数要用到这个宏定义，所以先定义一下：
#define small_const_nbits(nbits)
( __builtin_const_p(nbits) && (nbits) <= BITS_PER_LONG )
__builtin_const_p(n) 是gcc内嵌的用于判断一个变量的内容是不是一个常数；
所以 small_const_nbits()这个宏的主要作用是来判断一个变量的内容是否是一个常数，以及这两个变量的值是否大于32；
7.对位图进行初始化：
void bitmap_zero(unsigned long *bimap, int nbits)
{
//如果位图的长度小于32的话
if(small_const_nbits(nbits))
*bitmap = 0UL;
else
{
int length = BITS_TO_LONGS(nbits) * sizeof(long);
memset(bitmap, 0, length);
}
}
8.对位图进行填充：
void bitmap_fill(unsigned long *bitmap, int nbits)
{
if( small_const_nbits(nbits) )
*bitmap = BITS_TO_LONGS(nbits);
else
{
//最后的一个long数组元素可能并没有用完，所以只对用到的进行填充；
int length = BITS_TO_LONGS(nbits);
int len = (length - 1) * sizeof(long);
memset(bitmap, 0xff, len);
bitmap[length - 1] = BITS_TO_LONGS(nbits);
}
}
9.位图的拷贝：
void bitmap_copy(unsigned long *dest, unsigned long *src, int nbits)
{
if( small_const_nbits(nbits) )
*dest = *src;
else
{
int length = BITS_TO_LONGS(nbits) * sizeof(long);
memcpy(dest, src, length);
}
}
下面的这些函数只做说明，并不在介绍其是如何实现：
set_bit(int n, unsigned long *addr) //将addr位图中的第n位设置为1；
clear_bit(int n, unsigned long *addr) //将addr位图中的第n位置0；
change_bit(int n, unsigned long *addr) //将addr位图中的第n位改变，即1变0，0变1；
test_bit(int n, unsigned long *addr) //测试addr位图中的第n位是否为1；
test_and_set_bit(int n, unsigned long *addr)//测试addr位图中的第n位是否为1，如果不是
的话，将其设置为1，其返回值是之前第n位的值；
test_and_clear_bit(int n, unsigned long *addr);
test_and_change_bit(int n, unsigned long *addr);
unsigned int find_first_zero_bit(unsigned long *addr, int size) //在位图addr中，查找第一个为零的比特位，并返回其位置值；
find_first_bit(unsigned long *addr, int size) //在位图addr中，查找第一个为1的比特位，并返回其位置；
find_next_zero_bit(unsigned long *addr, int size, int pos) //在位图addr中，从pos开始
查找下一个为零的比特位，并返回其位置值；
fine_next_bit(unsigned long *addr, int size, int pos)
对位图进行遍历操作：
#define for_each_bit(bit, addr, size)
for( (bit) = find_firt_bit( (addr), (size) );
(bit) < (size);
(bit) = find_next_bit( (addr), (size), (bit)+1 ) )
在linux源代码中关于位图各种操作实现位于： /include/linux/bitmap.h
/include/linux/bitops.h
/lib/bitmap.c