[117] | 1 | /* +++Date last modified: 05-Jul-1997 */ |
---|
| 2 | |
---|
| 3 | /* |
---|
| 4 | ** BITCNT_4.C - Recursive bit counting functions using table lookup |
---|
| 5 | ** |
---|
| 6 | ** public domain by Bob Stout |
---|
| 7 | */ |
---|
| 8 | |
---|
| 9 | #include "bitcount-bitops.h" /* from Snippets */ |
---|
| 10 | |
---|
| 11 | static char bits[256] = |
---|
| 12 | { |
---|
| 13 | 0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, /* 0 - 15 */ |
---|
| 14 | 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, /* 16 - 31 */ |
---|
| 15 | 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, /* 32 - 47 */ |
---|
| 16 | 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, /* 48 - 63 */ |
---|
| 17 | 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, /* 64 - 79 */ |
---|
| 18 | 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, /* 80 - 95 */ |
---|
| 19 | 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, /* 96 - 111 */ |
---|
| 20 | 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, /* 112 - 127 */ |
---|
| 21 | 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, /* 128 - 143 */ |
---|
| 22 | 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, /* 144 - 159 */ |
---|
| 23 | 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, /* 160 - 175 */ |
---|
| 24 | 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, /* 176 - 191 */ |
---|
| 25 | 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, /* 192 - 207 */ |
---|
| 26 | 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, /* 208 - 223 */ |
---|
| 27 | 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, /* 224 - 239 */ |
---|
| 28 | 4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8 /* 240 - 255 */ |
---|
| 29 | }; |
---|
| 30 | |
---|
| 31 | /* |
---|
| 32 | ** Count bits in each nybble |
---|
| 33 | ** |
---|
| 34 | ** Note: Only the first 16 table entries are used, the rest could be |
---|
| 35 | ** omitted. |
---|
| 36 | */ |
---|
| 37 | |
---|
| 38 | int CDECL ntbl_bitcnt(long x) |
---|
| 39 | { |
---|
| 40 | int cnt = bits[(int)(x & 0x0000000FL)]; |
---|
| 41 | |
---|
| 42 | if (0L != (x >>= 4)) |
---|
| 43 | cnt += ntbl_bitcnt(x); |
---|
| 44 | |
---|
| 45 | return cnt; |
---|
| 46 | } |
---|
| 47 | |
---|
| 48 | /* |
---|
| 49 | ** Count bits in each byte |
---|
| 50 | */ |
---|
| 51 | |
---|
| 52 | int CDECL btbl_bitcnt(long x) |
---|
| 53 | { |
---|
| 54 | int cnt = bits[ ((char *)&x)[0] & 0xFF ]; |
---|
| 55 | |
---|
| 56 | if (0L != (x >>= 8)) |
---|
| 57 | cnt += btbl_bitcnt(x); |
---|
| 58 | return cnt; |
---|
| 59 | } |
---|
| 60 | |
---|
| 61 | #ifdef TEST |
---|
| 62 | |
---|
| 63 | #include <stdlib.h> |
---|
| 64 | #include "snip_str.h" /* For plural_text() macro */ |
---|
| 65 | |
---|
| 66 | main(int argc, char *argv[]) |
---|
| 67 | { |
---|
| 68 | long n; |
---|
| 69 | |
---|
| 70 | while(--argc) |
---|
| 71 | { |
---|
| 72 | int i; |
---|
| 73 | |
---|
| 74 | n = atol(*++argv); |
---|
| 75 | i = btbl_bitcnt(n); |
---|
| 76 | printf("%ld contains %d bit%s set\n", |
---|
| 77 | n, i, plural_text(i)); |
---|
| 78 | } |
---|
| 79 | return 0; |
---|
| 80 | } |
---|
| 81 | |
---|
| 82 | #endif /* TEST */ |
---|