| /* +++Date last modified: 05-Jul-1997 */ |
| |
| /* |
| ** BITCNT_3.C - Bit counting functions using table lookup |
| ** |
| ** public domain by Auke Reitsma and Bruce Wedding |
| */ |
| |
| #include "bitops.h" /* from Snippets */ |
| |
| /* |
| ** Bits table |
| */ |
| |
| 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_bitcount(long int x) |
| { |
| return |
| bits[ (int) (x & 0x0000000FUL) ] + |
| bits[ (int)((x & 0x000000F0UL) >> 4) ] + |
| bits[ (int)((x & 0x00000F00UL) >> 8) ] + |
| bits[ (int)((x & 0x0000F000UL) >> 12)] + |
| bits[ (int)((x & 0x000F0000UL) >> 16)] + |
| bits[ (int)((x & 0x00F00000UL) >> 20)] + |
| bits[ (int)((x & 0x0F000000UL) >> 24)] + |
| bits[ (int)((x & 0xF0000000UL) >> 28)]; |
| } |
| |
| /* |
| ** Count bits in each byte |
| ** |
| ** by Bruce Wedding, works best on Watcom & Borland |
| */ |
| |
| int CDECL BW_btbl_bitcount(long int x) |
| { |
| int xi = (int) x; |
| union |
| { |
| unsigned char ch[4]; |
| int y; |
| } U; |
| |
| U.y = xi; |
| |
| return bits[ U.ch[0] ] + bits[ U.ch[1] ] + |
| bits[ U.ch[3] ] + bits[ U.ch[2] ]; |
| } |
| |
| /* |
| ** Count bits in each byte |
| ** |
| ** by Auke Reitsma, works best on Microsoft, Symantec, and others |
| */ |
| |
| int CDECL AR_btbl_bitcount(long int x) |
| { |
| int xi = (int) x; |
| unsigned char * Ptr = (unsigned char *) &xi ; |
| int Accu ; |
| |
| Accu = bits[ *Ptr++ ]; |
| Accu += bits[ *Ptr++ ]; |
| Accu += bits[ *Ptr++ ]; |
| Accu += bits[ *Ptr ]; |
| return Accu; |
| } |
| |
| #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 = BW_btbl_bitcount(n); |
| printf("%ld contains %d bit%s set\n", |
| n, i, plural_text(i)); |
| i = AR_btbl_bitcount(n); |
| printf("%ld contains %d bit%s set\n", |
| n, i, plural_text(i)); |
| } |
| return 0; |
| } |
| |
| #endif /* TEST */ |