Blame view
lib/hweight.c
1.62 KB
3b9ed1a5d
|
1 |
#include <linux/module.h> |
1977f0327
|
2 |
#include <linux/bitops.h> |
3b9ed1a5d
|
3 4 5 6 7 8 9 10 11 12 13 |
#include <asm/types.h> /** * hweightN - returns the hamming weight of a N-bit word * @x: the word to weigh * * The Hamming Weight of a number is the total number of bits set in it. */ unsigned int hweight32(unsigned int w) { |
f9b419292
|
14 |
unsigned int res = w - ((w >> 1) & 0x55555555); |
3b9ed1a5d
|
15 |
res = (res & 0x33333333) + ((res >> 2) & 0x33333333); |
f9b419292
|
16 17 18 |
res = (res + (res >> 4)) & 0x0F0F0F0F; res = res + (res >> 8); return (res + (res >> 16)) & 0x000000FF; |
3b9ed1a5d
|
19 20 21 22 23 |
} EXPORT_SYMBOL(hweight32); unsigned int hweight16(unsigned int w) { |
f9b419292
|
24 |
unsigned int res = w - ((w >> 1) & 0x5555); |
3b9ed1a5d
|
25 |
res = (res & 0x3333) + ((res >> 2) & 0x3333); |
f9b419292
|
26 27 |
res = (res + (res >> 4)) & 0x0F0F; return (res + (res >> 8)) & 0x00FF; |
3b9ed1a5d
|
28 29 30 31 32 |
} EXPORT_SYMBOL(hweight16); unsigned int hweight8(unsigned int w) { |
f9b419292
|
33 |
unsigned int res = w - ((w >> 1) & 0x55); |
3b9ed1a5d
|
34 |
res = (res & 0x33) + ((res >> 2) & 0x33); |
f9b419292
|
35 |
return (res + (res >> 4)) & 0x0F; |
3b9ed1a5d
|
36 37 38 39 40 41 42 43 |
} EXPORT_SYMBOL(hweight8); unsigned long hweight64(__u64 w) { #if BITS_PER_LONG == 32 return hweight32((unsigned int)(w >> 32)) + hweight32((unsigned int)w); #elif BITS_PER_LONG == 64 |
0136611c6
|
44 45 46 47 48 49 |
#ifdef ARCH_HAS_FAST_MULTIPLIER w -= (w >> 1) & 0x5555555555555555ul; w = (w & 0x3333333333333333ul) + ((w >> 2) & 0x3333333333333333ul); w = (w + (w >> 4)) & 0x0f0f0f0f0f0f0f0ful; return (w * 0x0101010101010101ul) >> 56; #else |
f9b419292
|
50 |
__u64 res = w - ((w >> 1) & 0x5555555555555555ul); |
3b9ed1a5d
|
51 |
res = (res & 0x3333333333333333ul) + ((res >> 2) & 0x3333333333333333ul); |
f9b419292
|
52 53 54 55 |
res = (res + (res >> 4)) & 0x0F0F0F0F0F0F0F0Ful; res = res + (res >> 8); res = res + (res >> 16); return (res + (res >> 32)) & 0x00000000000000FFul; |
0136611c6
|
56 |
#endif |
3b9ed1a5d
|
57 58 59 |
#endif } EXPORT_SYMBOL(hweight64); |