home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #16 / NN_1992_16.iso / spool / sci / math / numanal / 2292 < prev    next >
Encoding:
Text File  |  1992-07-25  |  1.5 KB  |  69 lines
  1. Newsgroups: sci.math.num-analysis
  2. Path: sparky!uunet!infonode!ingr!analog!suhana!aaronb
  3. From: aaronb@suhana.analog.ingr.com (Aaron B.)
  4. Subject: Algorithm to find which bits set.
  5. Message-ID: <1992Jul26.013041.10387@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:30:41 GMT
  11. Lines: 56
  12.  
  13. Hi there:
  14.  
  15. My friend asked me the fastest way of finding which bits are
  16. set in a bit-string.  I gave him my first response.  But I think there
  17. is a better way of doing it.
  18.  
  19. If anybody have a better way of doing this please E-mail me your response.
  20.  
  21. Thanks in advance.
  22.  
  23. Aaron Bustamam
  24.  
  25. aaronb@suhana.analog.ingr.com
  26.  
  27. Here is my response:
  28.  
  29. static unsigned char binvalue[9]={0x00, 0x01, 0x02, 0x04, 0x08,
  30.                                         0x10, 0x20, 0x40, 0x80 };
  31.  
  32.  
  33. /*      Main function that will take any byte and display the bits position 
  34.     turn on.  off is the offset of the byte in the bit-string.
  35. */
  36.  
  37.  
  38. int
  39. show_msb(ch, off)
  40. unsigned char ch;
  41. long          off;
  42. {
  43.   int pos;
  44.  
  45.   if ( ch )
  46.    {
  47.      pos = ilog2( ch );
  48.      printf("position = %d\n",pos+off);
  49.      ch ^= binvalue[pos];         /* could also use: ch -= binvalue[pos]; */
  50.      show_msb(ch, off);           /* recursive call for rest of bits */
  51.    }
  52.   return( 0 );
  53. }
  54.  
  55. int
  56. ilog2(n)
  57. register unsigned char n;
  58. {
  59.    register long q;
  60.  
  61.    q = 0;
  62.    while( n )
  63.     {
  64.       n >>= 1;
  65.       q++;
  66.     }
  67.    return( q );
  68. }   /* ilog2 */
  69.