Linux系统位运算函数以及相应CPU ISA实现收录

以32位数据的二进制表示为例，习惯的写法是LSB在左，MSB在右，注意BIT序和大小端的字节序没有关系。

Linux和BIT操作有关的接口在定义在头文件bitops.h中，bitops.h定义有两层，通用层和架构层，对应两个bitops.h，通用层的定义在./include/linux/bitops.h中，架构层和处理器类型有关，定义在./arch/$ARCH/include/asm/bitops.h中。

除了这两个之外，实际上还有一个不常用到的include/asm-generic/bitops.h，这个头文件一般只能被include/linux/bitops.h引用

所以引用关系可以表示为：

arch目录下的bitops.h定义也仅允许被./include/linux/bitops.h引用。

如果./include/asm-generic/下的头文件没有直接被./include/linux/bitops.h引用，则也可以被ARCH下的头文件直接引用./arch/$ARCH/include/asm/bitops.h

下面分别介绍每个BITOPS函数：

ffs

ffs意思是Find First bit Set in word(From LSB to MSB).BIT从1开始记，返回值是[1,32],当输入0值时，返回是0,也就是ffs(0) = 0;ffs(1)=1, ffs(0x80000000)=32;所以算上返回0的情况，值域是[0,32].

__ffs

__ffs意思同样是Find First bit Set in word.(From LSB to MSB).与ffs不同的是，__ffs从0开始记数。由于返回0表示的是bit 0为1,所以没有一个合理返回值表达__ffs(0)，所以__ffs(0)没有定义，应用必须自行主动判断为0的情况，保证输入__ffs的参数为非0值。__ffs(0)=Undefined. __ffs(1) = 0; __ffs(0x80000000)=31;

__ffs/ffs相互实现:

int ffs(int x)
{
    if (!x) return 0;
    return __ffs(x) + 1;
}
 
int __ffs(int x)
{
    return ffs(x) - 1;
}

__ffs对参数的要求条件要强于ffs,所以_ffs的参数可以直接传给ffs，但是ffs的参数需要做0检查才能传递给__ffs。有点类似于C++基类和子类前置条件和后置条件的关系。

ffz

ffz means Find First Zero in word. 值域范围为[0,31].如果输入为0xFFFFFFFF，则结果未定义。在调用前，应用层因该进行条件检查。

ffz恰好是_ffs的逆运算而非ffs的逆运算。所以可以通过_ffs来实现ffz

#define ffz(x) _ffs(~(x))

clz

clz means "Count Leading Zeroes".计算前导0的个数，它从最高有效位（MSB）开始计算第一个位之前存在多少个零。在有些架构的处理器中，专门定义了"clz"指令用来完成此类运算，比如MIPS。

clz是下面将要介绍的fls的小伙伴和好助手，通过clz实现fls非常的简单和方便。由于它是一个计数值而非一个位置，所以值域并非前面的[0,31]或者[1,32],而是[0,32]. czl[0] = 32, czl(0xFFFFFFFF)=0,

clz(0x1)=31; clz(0x80000000)=0;

RISCV B扩展支持CLZ指令，B扩展几乎支持这篇文章讲到的所有BIT 操作指令，包括插入，提取，测试位域，COUNT BIT SET等等。

ctz

ctz means "Count Trailing Zeroes".它和clz有些类似，只是计算的是尾巴上（LSB)连续0的个数。它从最低有效位（LSB）开始计算第一个置位之前存在多少个零。

RISCV对此算法也有ISA指令级别的支持。

fls

fls means Find Last(Most Significant) bit set.和ffs恰恰相反，fls从LSB开始查找，找到最后一个值1的位，并返回其位置。值域为[1,32]. fls(0) = 0; fls(1) = 1; fls(0x80000000) = 32; 算上输入为0的情况，值域为[0,32]

fls可以通过clz实现：

fls(x) = 32-clz(x);

__fls

如同ffs和__ffs的关系一样，__fls也可以通过fls减1实现。同样对于0值，__fls不知如何处理，需要应用负责判断。

int __fls(unsigned long x)
{
    if(!x) return 0;
    else return fls(x) - 1;
}

hweight_long/hweight32/hweight64

返回一个数字的加权平衡值，一个数的加权平衡是这个数所有位的总和。定义在文件include/asm-generic/bitops/const_hweight.h

#include <stdio.h>
#include <stdlib.h>
#include "include/asm-generic/bitops/const_hweight.h"
 
int main(void)
{
        printf("%s line %d, %d, %d, %d.\n", __func__, __LINE__, hweight32(0), hweight32(0xffffffff), hweight32(0x08000000));
        return 0;
}

find_first_zero_bit

在内存中查找第一个值为0的位。

find_next_zero_bit

在内存中查找下一个值为0的位

bitfield实现

bitfield可以提取，写入，修改数据的指定BIT区域，内核中有bitfield.h文件定义对为域操作的接口：

参考资料

斯坦福大学关于位运算的算法总结：

https://graphics.stanford.edu/~seander/bithacks.html

结束

---