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