[117] | 1 | /* +++Date last modified: 05-Jul-1997 */ |
---|
| 2 | |
---|
| 3 | /* |
---|
| 4 | ** BITCNT_3.C - Bit counting functions using table lookup |
---|
| 5 | ** |
---|
| 6 | ** public domain by Auke Reitsma and Bruce Wedding |
---|
| 7 | */ |
---|
| 8 | |
---|
| 9 | #include "bitcount-bitops.h" /* from Snippets */ |
---|
| 10 | |
---|
| 11 | /* |
---|
| 12 | ** Bits table |
---|
| 13 | */ |
---|
| 14 | |
---|
| 15 | static char bits[256] = |
---|
| 16 | { |
---|
| 17 | 0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, /* 0 - 15 */ |
---|
| 18 | 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, /* 16 - 31 */ |
---|
| 19 | 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, /* 32 - 47 */ |
---|
| 20 | 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, /* 48 - 63 */ |
---|
| 21 | 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, /* 64 - 79 */ |
---|
| 22 | 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, /* 80 - 95 */ |
---|
| 23 | 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, /* 96 - 111 */ |
---|
| 24 | 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, /* 112 - 127 */ |
---|
| 25 | 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, /* 128 - 143 */ |
---|
| 26 | 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, /* 144 - 159 */ |
---|
| 27 | 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, /* 160 - 175 */ |
---|
| 28 | 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, /* 176 - 191 */ |
---|
| 29 | 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, /* 192 - 207 */ |
---|
| 30 | 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, /* 208 - 223 */ |
---|
| 31 | 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, /* 224 - 239 */ |
---|
| 32 | 4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8 /* 240 - 255 */ |
---|
| 33 | }; |
---|
| 34 | |
---|
| 35 | /* |
---|
| 36 | ** Count bits in each nybble |
---|
| 37 | ** |
---|
| 38 | ** Note: Only the first 16 table entries are used, the rest could be |
---|
| 39 | ** omitted. |
---|
| 40 | */ |
---|
| 41 | |
---|
| 42 | int CDECL ntbl_bitcount(long int x) |
---|
| 43 | { |
---|
| 44 | return |
---|
| 45 | bits[ (int) (x & 0x0000000FUL) ] + |
---|
| 46 | bits[ (int)((x & 0x000000F0UL) >> 4) ] + |
---|
| 47 | bits[ (int)((x & 0x00000F00UL) >> 8) ] + |
---|
| 48 | bits[ (int)((x & 0x0000F000UL) >> 12)] + |
---|
| 49 | bits[ (int)((x & 0x000F0000UL) >> 16)] + |
---|
| 50 | bits[ (int)((x & 0x00F00000UL) >> 20)] + |
---|
| 51 | bits[ (int)((x & 0x0F000000UL) >> 24)] + |
---|
| 52 | bits[ (int)((x & 0xF0000000UL) >> 28)]; |
---|
| 53 | } |
---|
| 54 | |
---|
| 55 | /* |
---|
| 56 | ** Count bits in each byte |
---|
| 57 | ** |
---|
| 58 | ** by Bruce Wedding, works best on Watcom & Borland |
---|
| 59 | */ |
---|
| 60 | |
---|
| 61 | int CDECL BW_btbl_bitcount(long int x) |
---|
| 62 | { |
---|
| 63 | union |
---|
| 64 | { |
---|
| 65 | unsigned char ch[4]; |
---|
| 66 | long y; |
---|
| 67 | } U; |
---|
| 68 | |
---|
| 69 | U.y = x; |
---|
| 70 | |
---|
| 71 | return bits[ U.ch[0] ] + bits[ U.ch[1] ] + |
---|
| 72 | bits[ U.ch[3] ] + bits[ U.ch[2] ]; |
---|
| 73 | } |
---|
| 74 | |
---|
| 75 | /* |
---|
| 76 | ** Count bits in each byte |
---|
| 77 | ** |
---|
| 78 | ** by Auke Reitsma, works best on Microsoft, Symantec, and others |
---|
| 79 | */ |
---|
| 80 | |
---|
| 81 | int CDECL AR_btbl_bitcount(long int x) |
---|
| 82 | { |
---|
| 83 | unsigned char * Ptr = (unsigned char *) &x ; |
---|
| 84 | int Accu ; |
---|
| 85 | |
---|
| 86 | Accu = bits[ *Ptr++ ]; |
---|
| 87 | Accu += bits[ *Ptr++ ]; |
---|
| 88 | Accu += bits[ *Ptr++ ]; |
---|
| 89 | Accu += bits[ *Ptr ]; |
---|
| 90 | return Accu; |
---|
| 91 | } |
---|
| 92 | |
---|
| 93 | #ifdef TEST |
---|
| 94 | |
---|
| 95 | #include <stdlib.h> |
---|
| 96 | #include "snip_str.h" /* For plural_text() macro */ |
---|
| 97 | |
---|
| 98 | main(int argc, char *argv[]) |
---|
| 99 | { |
---|
| 100 | long n; |
---|
| 101 | |
---|
| 102 | while(--argc) |
---|
| 103 | { |
---|
| 104 | int i; |
---|
| 105 | |
---|
| 106 | n = atol(*++argv); |
---|
| 107 | i = BW_btbl_bitcount(n); |
---|
| 108 | printf("%ld contains %d bit%s set\n", |
---|
| 109 | n, i, plural_text(i)); |
---|
| 110 | i = AR_btbl_bitcount(n); |
---|
| 111 | printf("%ld contains %d bit%s set\n", |
---|
| 112 | n, i, plural_text(i)); |
---|
| 113 | } |
---|
| 114 | return 0; |
---|
| 115 | } |
---|
| 116 | |
---|
| 117 | #endif /* TEST */ |
---|