home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #16 / NN_1992_16.iso / spool / comp / compress / research / 91 < prev    next >
Encoding:
Text File  |  1992-07-25  |  1.4 KB  |  61 lines
  1. Newsgroups: comp.compression.research
  2. Path: sparky!uunet!infonode!ingr!analog!suhana!aaronb
  3. From: aaronb@suhana.analog.ingr.com (Aaron B.)
  4. Subject: Algorithm for finding set bits in a bit-string.
  5. Message-ID: <1992Jul26.010325.9885@infonode.ingr.com>
  6. Keywords: Bit counting.
  7. Sender: harun@suhana (Aaron B.)
  8. Reply-To: aaronb@suhana.analog.ingr.com
  9. Organization: Home Office Enterprise
  10. Date: Sun, 26 Jul 1992 01:03:25 GMT
  11. Lines: 48
  12.  
  13. I don't know where this request should belong, this is the closest group
  14. I can find.  Anyway, this is my problem (my friend's actually):
  15.  
  16. Given a bit-string of any size print out the bits set starting with the
  17. least significant bit.  This is an algorithm that I offered him.  But I
  18. think there is much better way of doing it.
  19.  
  20.  
  21. static unsigned char binvalue[9]={0x00, 0x01, 0x02, 0x04, 0x08,
  22.                                         0x10, 0x20, 0x40, 0x80 };
  23.  
  24. int
  25. show_msb(ch, off)
  26. unsigned char ch;
  27. long          off;
  28. {
  29.   int pos;
  30.  
  31.   if ( ch )
  32.    {
  33.      pos = ilog2( ch );
  34.      printf("position = %d\n",pos+off);
  35.      ch ^= binvalue[pos];         /* could also use: ch -= binvalue[pos]; */
  36.      show_msb(ch, off);           /* recursive call for rest of bits */
  37.    }
  38.   return( 0 );
  39. }
  40.  
  41. int
  42. ilog2(n)
  43. register unsigned char n;
  44. {
  45.    register long q;
  46.  
  47.    q = 0;
  48.    while( n )
  49.     {
  50.       n >>= 1;
  51.       q++;
  52.     }
  53.    return( q );
  54. }   /* ilog2 */
  55.  
  56.  
  57. Thanks in advance.
  58.  
  59. Aaron B
  60. aaronb@suhana.analog.ingr.com
  61.