原文地址：http://blog.csdn.net/benny5609/article/details/2194823
在底层软件开发过程中经常使用位掩码标识一个状态符号。举一个例子来说，比如一个U32类型的变量Use_Mask用来表示32个内存块的占用状态，变量的每一位代表一个内存块的使用状态，1b表示空闲，0b表示被占用。当应用程序需要使用一个空闲块时，只需要查询Use_Mask哪一位为1，就可以直接将给Bit位对应的内存块拿来使用了，当然在使用前将该位置1了。同理，使用完给内存块后，也需要将对应位置0就可以了。 那么，如何根据Use_Mask得到为1位的位置呢，比较直接的方法如下： int GetUnUseMem(U32 UseMask) { int i; U32 temp=UseMask; for(i=0;i<32;i++) { if(temp &0x00000001) return i； temp= temp>>1; } return -1; } 显然，用这种方法可以得到期望的结果，但是该函数的计算量是与输入参数的内容相关的，最坏情况的运算时间可能是最好情况的32倍。这在一些实时要求比较高的系统中是很难接受的。同时，在函数代码中存在循环，判断分支，也非常不适合当前具有预取指令，乱序执行等功能的处理器提高其性能。当然，我们可以将循环展开，定义寄存器变量等技巧来解决一部分问题，但是是否有其它方法吗。这里考虑了两种方案，抛砖引玉：
1、查找表
该方法一般在掩码长度为8位时比较常见，即定义一个数组X，数组长度为2 的n次方，n为掩码的长度。如掩码为8位时可定义一个256个单元的数组，数组第m个单元初始化为但掩码值为m时其第一个为1位的位置，比如m=0xF4，则11110100b，其第一个为一的位在bit2上，则X[m]=2，同理但X[0xF5]=0，当然X[0x00]=-1。有了这张表，那么查找比特1位置的函数实现很简单：
int X[256]={-1，0，1，0，...} int GetUnUseMem(U8 UseMask)
{
return X[
UseMask
];
}
那么问题是当
UseMask为32位时怎么办，难道构建2的32次方长度的数组吗，也即4G个单元，当然不好，除非你要想搞死你的机器。那就分段处理吧。
int GetUnUseMem(U32 UseMask)
{ int Ret; if((
Ret=
X[
UseMask&0x
FF]
)>=0) goto
GetUnUseMem_End;
if((
Ret=
(X[
UseMask&0x
FF00 >>8] +8)
)>=0) goto
GetUnUseMem_End;
if((
Ret=
(X[
UseMask&0x
FF0000 >>16] +16)
)>=0) goto
GetUnUseMem_End;
Ret=
X[
UseMask&0x
FF000000 >>24] +24;
GetUnUseMem_End:
return Ret;
}
如果是64位的掩码呢，最多要判断8次，显然不合适，因此可以使用两级解码，第一级掩码中一位代表下一级掩码的相应8位是否有1。
int X[256]={-1，0，1，0，...} U8
Y[256]={0，0，8，0，16, 0 ,...}
int GetUnUseMem(U8 UseMask1,
U64 UseMask)
{ register U8 index =
Y[
UseMask
1]
; index = (U8)(UseMask2>>index
& 0xFF);
return X[
index
];
}
2、位运算
使用位运算可以更快的得到，也不需要用查找表占用内存空间，由于访问内存非常影响处理器的效率，而使用这种方式会使用寄存器或者CPU缓存，不通过北桥再经过DDRII内存控制器得到，因此效率比查找表要高。
int GetUnUseMem(
U32 UseMask)
{ register U32 index =
UseMask
; //将第一个为1位的低位都置1，其它位都置0 index = (index-1) & ~index;
//得到有多少为1的位
index = index&0x55555555 + (index>>1)&0x55555555; index = index&0x33333333+
(index>>2)&0x33333333;
index = index&0x0F0F0F0F+
(index>>4)&0x0F0F0F0F;
index = index&0xFF + (index&0xFF00 >> 8) +
(index&0xFF0000 >> 16) +
(index&0xFF000000 >> 24)
; //得到位数,如果为32则表示全0
return (int)(index)
;
}
