| /* +++Date last modified: 05-Jul-1997 */ |
| |
| /* |
| ** BITCNT_4.C - Recursive bit counting functions using table lookup |
| ** |
| ** public domain by Bob Stout |
| */ |
| |
| #include "bitops.h" /* from Snippets */ |
| |
| static char bits[256] = |
| { |
| 0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, /* 0 - 15 */ |
| 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, /* 16 - 31 */ |
| 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, /* 32 - 47 */ |
| 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, /* 48 - 63 */ |
| 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, /* 64 - 79 */ |
| 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, /* 80 - 95 */ |
| 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, /* 96 - 111 */ |
| 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, /* 112 - 127 */ |
| 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, /* 128 - 143 */ |
| 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, /* 144 - 159 */ |
| 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, /* 160 - 175 */ |
| 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, /* 176 - 191 */ |
| 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, /* 192 - 207 */ |
| 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, /* 208 - 223 */ |
| 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, /* 224 - 239 */ |
| 4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8 /* 240 - 255 */ |
| }; |
| |
| /* |
| ** Count bits in each nybble |
| ** |
| ** Note: Only the first 16 table entries are used, the rest could be |
| ** omitted. |
| */ |
| |
| int CDECL ntbl_bitcnt(long x) |
| { |
| int cnt = bits[(int)(x & 0x0000000FL)]; |
| |
| if (0L != (x >>= 4)) |
| cnt += ntbl_bitcnt(x); |
| |
| return cnt; |
| } |
| |
| /* |
| ** Count bits in each byte |
| */ |
| |
| int CDECL btbl_bitcnt(long x) |
| { |
| int cnt = bits[ ((char *)&x)[0] & 0xFF ]; |
| |
| if (0L != (x >>= 8)) |
| cnt += btbl_bitcnt(x); |
| return cnt; |
| } |
| |
| #ifdef TEST |
| |
| #include <stdlib.h> |
| #include "snip_str.h" /* For plural_text() macro */ |
| |
| main(int argc, char *argv[]) |
| { |
| long n; |
| |
| while(--argc) |
| { |
| int i; |
| |
| n = atol(*++argv); |
| i = btbl_bitcnt(n); |
| printf("%ld contains %d bit%s set\n", |
| n, i, plural_text(i)); |
| } |
| return 0; |
| } |
| |
| #endif /* TEST */ |