home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 10 Tools / 10-Tools.zip / snip9707.zip / BITCNT_3.C < prev    next >
C/C++ Source or Header  |  1997-07-05  |  3KB  |  118 lines
  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 "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 */
  118.