[toc]

在这里插入图片描述

include/asm-generic/bitops/const_hweight.h

lib/hweight.c

软件汉明权重计算：__sw_hweight 系列函数

本代码片段提供了一组用于计算不同位宽整数（8、16、32、64位）汉明权重（Hamming Weight）的纯软件实现。汉明权重，又称“置位比特计数”（population count），指的是一个二进制数中 ‘1’ 的总个数。这些函数是内核中需要进行位操作统计时的基础工具，其实现采用了高效的、不依赖特定处理器指令的“分治”并行算法。

实现原理分析

这些函数的核心是采用了一种经典的分治算法（Divide and Conquer），在对数时间内完成计算，远比逐位检查的方法高效。以 __sw_hweight32 为例，其算法步骤如下：

  1. 两比特分组求和:
    w -= (w >> 1) & 0x55555555;

    • 0x55555555 的二进制表示为 01010101...。
    • (w >> 1) & 0x55555555 的作用是分离出 w 中每两个比特位中的高位。
    • 将 w 减去这个值，其效果是在每个两比特的“窗口”内，独立地计算出 ‘1’ 的个数。例如，对于两位 b1b0，其计算为 (b1*2 + b0) - b1 = b1 + b0。运算后，w 的每两位存储了原始数值对应位置两位中 ‘1’ 的个数。

  2. 四比特分组求和:
    w = (w & 0x33333333) + ((w >> 2) & 0x33333333);

    • 0x33333333 的二进制表示为 00110011...。
    • w & 0x33333333 取出上一步中每四位里的低两位（即第一个两比特分组的和）。
    • (w >> 2) & 0x33333333 取出高两位（即第二个两比特分组的和）。
    • 将两者相加，就在每个四比特的窗口内，得到了 ‘1’ 的总数。

  3. 八比特（字节）分组求和:
    w = (w + (w >> 4)) & 0x0f0f0f0f;

    • 0x0f0f0f0f 的二进制表示为 00001111...。
    • 此步骤将相邻的两个四比特分组的和相加，得到每个字节（8位）中 ‘1’ 的总数。

  4. 最终求和（两种策略）:

    • 快速乘法器策略 (CONFIG_ARCH_HAS_FAST_MULTIPLIER):
      return (w * 0x01010101) >> 24;
      这是一个非常巧妙的技巧。此时 w 的四个字节分别存储了原始数值对应四个字节的汉明权重。将 w 乘以 0x01010101，其效果会将所有字节的和累加到结果的最高字节中。右移24位即可分离出这个最终总和。此方法依赖于一个高效的硬件乘法器。
    • 移位与加法策略:
      res = res + (res >> 8); return (res + (res >> 16)) & 0x000000FF;
      这是一种不依赖乘法器的通用方法。它通过移位和加法，先将相邻字节的和累加，再将相邻16位半字的和累加，最终结果会汇集到最低的字节中，通过与 0xFF 相与即可得到。

其他函数如 __sw_hweight16 和 __sw_hweight8 遵循完全相同的算法逻辑，只是使用的位掩码和移位数不同。__sw_hweight64 则根据系统的字长（BITS_PER_LONG）来决定实现方式。

代码分析

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
// SPDX-License-Identifier: GPL-2.0
#include <linux/export.h>
#include <linux/bitops.h>
#include <asm/types.h>

/**
 * hweightN - 返回 N 位字的汉明权重
 * @x: 需要计算权重的字
 *
 * 一个数的汉明权重是其中被置位的比特的总数。
 */

/**
 * @brief __sw_hweight32 - 计算32位无符号整数的汉明权重。
 * @param w: 32位输入值。
 * @return unsigned int: 输入值中'1'的个数。
 */
unsigned int __sw_hweight32(unsigned int w)
{
// 如果目标架构有快速硬件乘法器。
#ifdef CONFIG_ARCH_HAS_FAST_MULTIPLIER
	// 步骤1: 累加每2个比特位的'1'。结果存储在2比特的窗口中。
	w -= (w >> 1) & 0x55555555;
	// 步骤2: 累加每4个比特位的'1'。结果存储在4比特的窗口中。
	w =  (w & 0x33333333) + ((w >> 2) & 0x33333333);
	// 步骤3: 累加每8个比特位的'1'。结果存储在8比特的窗口中（字节）。
	w =  (w + (w >> 4)) & 0x0f0f0f0f;
	// 步骤4: 将所有字节的和累加到最高字节，然后返回。
	return (w * 0x01010101) >> 24;
#else
	// 如果没有快速乘法器，采用移位和加法策略。
	unsigned int res = w - ((w >> 1) & 0x55555555);
	res = (res & 0x33333333) + ((res >> 2) & 0x33333333);
	res = (res + (res >> 4)) & 0x0F0F0F0F;
	// 步骤4a: 累加相邻字节。
	res = res + (res >> 8);
	// 步骤4b: 累加相邻半字，最终结果在最低字节，屏蔽后返回。
	return (res + (res >> 16)) & 0x000000FF;
#endif
}
EXPORT_SYMBOL(__sw_hweight32);

/**
 * @brief __sw_hweight16 - 计算16位无符号整数的汉明权重。
 * @param w: 16位输入值。
 * @return unsigned int: 输入值中'1'的个数。
 */
unsigned int __sw_hweight16(unsigned int w)
{
	// 算法与32位版本相同，但使用16位的掩码和移位数。
	unsigned int res = w - ((w >> 1) & 0x5555);
	res = (res & 0x3333) + ((res >> 2) & 0x3333);
	res = (res + (res >> 4)) & 0x0F0F;
	return (res + (res >> 8)) & 0x00FF;
}
EXPORT_SYMBOL(__sw_hweight16);

/**
 * @brief __sw_hweight8 - 计算8位无符号整数的汉明权重。
 * @param w: 8位输入值。
 * @return unsigned int: 输入值中'1'的个数。
 */
unsigned int __sw_hweight8(unsigned int w)
{
	// 算法与32位版本相同，但使用8位的掩码和移位数。
	unsigned int res = w - ((w >> 1) & 0x55);
	res = (res & 0x33) + ((res >> 2) & 0x33);
	return (res + (res >> 4)) & 0x0F;
}
EXPORT_SYMBOL(__sw_hweight8);

/**
 * @brief __sw_hweight64 - 计算64位无符号整数的汉明权重。
 * @param w: 64位输入值。
 * @return unsigned long: 输入值中'1'的个数。
 */
unsigned long __sw_hweight64(__u64 w)
{
// 如果系统是32位架构 (long类型是32位)。
#if BITS_PER_LONG == 32
	// 将64位输入拆分为高32位和低32位，分别计算后相加。
	return __sw_hweight32((unsigned int)(w >> 32)) +
	       __sw_hweight32((unsigned int)w);
// 如果系统是64位架构 (long类型是64位)。
#elif BITS_PER_LONG == 64
	// 算法与32位版本相同，但使用64位的掩码和移位数。
#ifdef CONFIG_ARCH_HAS_FAST_MULTIPLIER
	w -= (w >> 1) & 0x5555555555555555ul;
	w =  (w & 0x3333333333333333ul) + ((w >> 2) & 0x3333333333333333ul);
	w =  (w + (w >> 4)) & 0x0f0f0f0f0f0f0f0ful;
	return (w * 0x0101010101010101ul) >> 56;
#else
	__u64 res = w - ((w >> 1) & 0x5555555555555555ul);
	res = (res & 0x3333333333333333ul) + ((res >> 2) & 0x3333333333333333ul);
	res = (res + (res >> 4)) & 0x0F0F0F0F0F0F0F0Ful;
	res = res + (res >> 8);
	res = res + (res >> 16);
	return (res + (res >> 32)) & 0x00000000000000FFul;
#endif
#endif
}
EXPORT_SYMBOL(__sw_hweight64);