]>
git.proxmox.com Git - mirror_ubuntu-artful-kernel.git/blob - lib/hweight.c
1 #include <linux/module.h>
5 * hweightN - returns the hamming weight of a N-bit word
6 * @x: the word to weigh
8 * The Hamming Weight of a number is the total number of bits set in it.
11 unsigned int hweight32(unsigned int w
)
13 unsigned int res
= (w
& 0x55555555) + ((w
>> 1) & 0x55555555);
14 res
= (res
& 0x33333333) + ((res
>> 2) & 0x33333333);
15 res
= (res
& 0x0F0F0F0F) + ((res
>> 4) & 0x0F0F0F0F);
16 res
= (res
& 0x00FF00FF) + ((res
>> 8) & 0x00FF00FF);
17 return (res
& 0x0000FFFF) + ((res
>> 16) & 0x0000FFFF);
19 EXPORT_SYMBOL(hweight32
);
21 unsigned int hweight16(unsigned int w
)
23 unsigned int res
= (w
& 0x5555) + ((w
>> 1) & 0x5555);
24 res
= (res
& 0x3333) + ((res
>> 2) & 0x3333);
25 res
= (res
& 0x0F0F) + ((res
>> 4) & 0x0F0F);
26 return (res
& 0x00FF) + ((res
>> 8) & 0x00FF);
28 EXPORT_SYMBOL(hweight16
);
30 unsigned int hweight8(unsigned int w
)
32 unsigned int res
= (w
& 0x55) + ((w
>> 1) & 0x55);
33 res
= (res
& 0x33) + ((res
>> 2) & 0x33);
34 return (res
& 0x0F) + ((res
>> 4) & 0x0F);
36 EXPORT_SYMBOL(hweight8
);
38 unsigned long hweight64(__u64 w
)
40 #if BITS_PER_LONG == 32
41 return hweight32((unsigned int)(w
>> 32)) + hweight32((unsigned int)w
);
42 #elif BITS_PER_LONG == 64
44 res
= (w
& 0x5555555555555555ul
) + ((w
>> 1) & 0x5555555555555555ul
);
45 res
= (res
& 0x3333333333333333ul
) + ((res
>> 2) & 0x3333333333333333ul
);
46 res
= (res
& 0x0F0F0F0F0F0F0F0Ful
) + ((res
>> 4) & 0x0F0F0F0F0F0F0F0Ful
);
47 res
= (res
& 0x00FF00FF00FF00FFul
) + ((res
>> 8) & 0x00FF00FF00FF00FFul
);
48 res
= (res
& 0x0000FFFF0000FFFFul
) + ((res
>> 16) & 0x0000FFFF0000FFFFul
);
49 return (res
& 0x00000000FFFFFFFFul
) + ((res
>> 32) & 0x00000000FFFFFFFFul
);
51 #error BITS_PER_LONG not defined
54 EXPORT_SYMBOL(hweight64
);