home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #16 / NN_1992_16.iso / spool / comp / arch / 8358 < prev    next >
Encoding:
Text File  |  1992-07-27  |  2.3 KB  |  89 lines
  1. Newsgroups: comp.arch
  2. Path: sparky!uunet!infonode!ingr!analog!suhana!aaronb
  3. From: aaronb@suhana.analog.ingr.com (Aaron B.)
  4. Subject: Finding which bit set in a bit-string.
  5. Message-ID: <1992Jul27.212607.26361@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: Mon, 27 Jul 1992 21:26:07 GMT
  11. Lines: 76
  12.  
  13.  
  14. Article: 93 of comp.compression.research
  15. Path: infonode!uunet!dtix!darwin.sura.net!mips!zaphod.mps.ohio-state.edu!caen!nic.umass.edu!dime!dime.cs.umass.edu!moss
  16. From: moss@cs.umass.edu (Eliot Moss)
  17. Newsgroups: comp.compression.research
  18. Subject: Re: Algorithm for finding set bits in a bit-string.
  19. Message-ID: <MOSS.92Jul25222337@ibis.cs.umass.edu>
  20. Date: 26 Jul 92 02:23:37 GMT
  21. References: <1992Jul26.010325.9885@infonode.ingr.com>
  22. Sender: news@dime.cs.umass.edu
  23. Reply-To: moss@cs.umass.edu
  24. Organization: Dept of Comp and Info Sci, Univ of Mass (Amherst)
  25. Lines: 17
  26.  
  27. I posted this on "comp.compression":
  28.  
  29. >Given a bit-string of any size print out the bits set starting with the
  30. >least significant bit.
  31.  
  32. And somebody reply with this:
  33.  
  34. >In-reply-to: aaronb@suhana.analog.ingr.com's message of 26 Jul 92 01:03:25 GMT
  35. >The "find first set bit" operation was recently discussed at length in
  36. >comp.arch, and could be relevant, especially if the one bits are sparse.
  37.  
  38. My question is: did anybody follow this thread in this group.  Is there anyway
  39. I could get access to the archive of this group.  If anybody had save the
  40. postings on this topic please E-mail me a copy.
  41.  
  42.  
  43. This is my current solution for this problem.  If anybody have a better one
  44. please E-mail your response.  Thanks.
  45.  
  46.  
  47. static unsigned char binvalue[9]={0x00, 0x01, 0x02, 0x04, 0x08,
  48.                                         0x10, 0x20, 0x40, 0x80 };
  49.  
  50. int
  51. show_msb(ch, off)
  52. unsigned char ch;
  53. long          off;
  54. {
  55.   int pos;
  56.  
  57.   if ( ch )
  58.    {
  59.      pos = ilog2( ch );
  60.      printf("position = %d\n",pos+off);
  61.      ch ^= binvalue[pos];         /* could also use: ch -= binvalue[pos]; */
  62.      show_msb(ch, off);           /* recursive call for rest of bits */
  63.    }
  64.   return( 0 );
  65. }
  66.  
  67. int
  68. ilog2(n)
  69. register unsigned char n;
  70. {
  71.    register long q;
  72.  
  73.    q = 0;
  74.    while( n )
  75.     {
  76.       n >>= 1;
  77.       q++;
  78.     }
  79.    return( q );
  80. }   /* ilog2 */
  81.  
  82.  
  83. Thanks in advance.
  84.  
  85. Aaron B
  86. aaronb@suhana.analog.ingr.com
  87.  
  88.  
  89.