对Linux kernel中 generic_hweight32函数的理解 收藏
generic_hweight32
Hamming weight is the number of "1" bits in the binary sequence.
/*
* hweightN: returns the hamming weight (i.e. the number
* of bits set) of a N-bit word.
*/
求32位二进制数中的'1'的个数：
static inline unsigned int generic_hweight32(unsigned int w)
{
unsigned int res = (w & 0x55555555) + ((w >> 1) & 0x55555555);
res = (res & 0x33333333) + ((res >> 2) & 0x33333333);
res = (res & 0x0F0F0F0F) + ((res >> 4) & 0x0F0F0F0F);
res = (res & 0x00FF00FF) + ((res >> 8) & 0x00FF00FF);
return (res & 0x0000FFFF) + ((res >> 16) & 0x0000FFFF);
}
分析：
这个函数的目的是求32位二进制数中的'1'的个数，我认为主要用到的思想就是算法中的"分治法"。以最为极端的情况来考虑
即w = 0xFFFFFFFF。
1）.unsigned int res = (w & 0x55555555) + ((w >> 1) & 0x55555555);
这里需要注意一点：w的类型为unsigned int(无符号整型，32位)，因此，当w左移时，无论w的最高位是否为1，高位都用0补充。
w = 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 UL
-- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- --
[array32] 32 31 30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1
res = ( 0xFFFFFFFF & 0x55555555 ) + ( ( 0xFFFFFFFF >> 1 ) & 0x55555555 )
= 0x55555555 + ( 0x7FFFFFFF & 0x55555555 )
= 0x55555555 + 0x55555555
= 0xAAAAAAAA
= 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 UL
-- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- --
[array16] 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1
[array]是我为这个32位数标注的组号。
w当然就是一个有32个元素的组，我的目的不是要找到这32个元素中有多少个"1"么？好了，这里用到的最重要的思想就是：相邻组相加！！注意相邻组不是相邻位。第一次，相邻组就是1+2，3+4，5+6，... 31+32，这样加过来就从array32变成了array16了，函数的第一条语句相当于执行了16个运算！！！！
这里用图表示会更加形象：
-- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- --
w = 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 UL
-- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- --
[array32] 32 31 30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | |
->+| ->+| ->+| ->+| ->+| ->+| ->+| ->+| ->+| ->+| ->+| ->+| ->+| ->+| ->+| ->+|
V V V V V V V V V V V V V V V V
---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- --
res =1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 UL
---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- --
[array16] 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1
2). 如此将数组维度继续缩小，相邻组相加，这次是1+2, 3+4, 5+6, ... 15+16,这样将array16变为array8... 直到array中只剩下一个元素，所有的"1"就都加在了一起。
如图所示：
---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- --
res = 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 UL
---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- --
[array16] 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1
| | | | | | | | | | | | | | | |
-->+| -->+| --->+| -->+| -->+| --->+| -->+| --->+|
V V V V V V V V
---------- ---------- ---------- ---------- ---------- ---------- ---------- ---------- --
res = 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 UL
---------- ---------- ---------- ---------- ---------- ---------- ---------- ---------- --
[array8] 8 7 6 5 4 3 2 1
| | | | | | | |
--------->+| --------->+| --------->+| --------->+|
V V V V
------------------------- ------------------------ ------------------------ ------------------------ --
res = 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 UL
------------------------- ------------------------ ------------------------ ------------------------ --
[array4] 4 3 2 1
| | | |
---------------------->+| ----------------------->+|
V V
-------------------------------------------------- --------------------------------------------------- --
res = 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 UL
-------------------------------------------------- --------------------------------------------------- --
[array2] 2 1
| |
--------------------------------------------------->+|
V
------------------------------------------------------------------------------------------------------ --
res = 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 UL
------------------------------------------------------------------------------------------------------ --
[array1] 1
|
V
32
这样一来，五条语句相当于执行了16+8+4+2+1 = 31个运算了！！！！
下面是我自己写的一个模仿程序，以验证这个算法。该程序找到一个无符号8位数中"1"的个数
#include <stdio.h>
#include <linux/types.h>
static int my_hweight8( __u8 w )
{
__u8 ret = ( w & 0x55 ) + ( ( w >> 1 ) & 0x55 );
ret = ( ret & 0x33 ) + ( ( ret >> 2 ) & 0x33 );
ret = ( ret & 0x0F ) + ( ( ret >> 4 ) & 0x0F );
return (int)ret;
}__attribute__((always_inline))
int main()
{
int get_hweight8 = my_hweight8(0x6D);
printf("there are %d '1' in my 0x6D/n", get_hweight8);
return 0;
}