home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1993 #1 / NN_1993_1.iso / spool / comp / sys / mac / programm / 20786 < prev    next >
Encoding:
Text File  |  1993-01-06  |  2.1 KB  |  59 lines
  1. Newsgroups: comp.sys.mac.programmer
  2. Path: sparky!uunet!news.univie.ac.at!chx400!bernina!bernina!neeri
  3. From: neeri@iis.ethz.ch (Matthias Neeracher)
  4. Subject: Re: (Q) Need bit manipulation algorithm
  5. In-Reply-To: lim@toadflax.cs.ucdavis.edu's message of 6 Jan 93 10:19:11 GMT
  6. Message-ID: <NEERI.93Jan6143512@iis.ethz.ch>
  7. Sender: news@bernina.ethz.ch (USENET News System)
  8. Organization: Integrated Systems Laboratory, ETH, Zurich
  9. References: <1993Jan6.022430.19469@leland.Stanford.EDU>
  10.     <1993Jan6.032113.597@planets.risc.rockwell.com>
  11.     <20751@ucdavis.ucdavis.edu>
  12. Date: Wed, 6 Jan 1993 13:35:12 GMT
  13. Lines: 44
  14.  
  15. In article <20751@ucdavis.ucdavis.edu>, lim@toadflax.cs.ucdavis.edu (Lloyd Lim) writes:
  16.  
  17. > In article <1993Jan6.032113.597@planets.risc.rockwell.com> sho@risc.rockwell.com (Sho Kuwamoto) writes:
  18. >>
  19. >>Maybe not the fastest method, but a simple one:
  20. >>   1) come up with an algorithm which counts the number of
  21. >>      1's in a given bit pattern.  You'll either use a loop
  22. >>      with shifts and increments in it, or you'll use masks.
  23. >>[...]
  24.  
  25. > There is a neat trick for counting the number of bits in a word that
  26. > a Microsoft geek showed me one time.  If there are k bits with 1's,
  27. > it runs in O(k) time.
  28.  
  29. > I don't remember the algorithm, but it involved subtracting 1 and could
  30. > be written in one line of C.  (Yeah, I know...  You could write anything,
  31. > even Microsoft Word, in one very long line of C code.  Come to think of it,
  32. > that's probably what they did.)  The subtraction was used to create
  33. > instant masks: e.g. 0x0100 - 1 = 0x00FF.  It went from the highest 1 bit
  34. > to the lowest, magically avoiding all of the 0's.
  35.  
  36. > That's all I remember.  Anyone remember this algorithm?
  37.  
  38. Sure.
  39.  
  40. int count_bits(int x)
  41. {
  42.    /* Return the number of 1 bits in x. Patent pending... NOT! */
  43.    int bitcnt;
  44.  
  45.    for (bitcnt=0; x; ++bitcnt)
  46.     x &= (x-1);
  47.  
  48.    return bitcnt;
  49. }
  50.  
  51. For the Pascal heathens out there: If an integer x has n 1-bits (n>1),
  52. BitAnd(x,x-1) will have (n-1) 1-bits.
  53.  
  54. Matthias
  55.  
  56. -----
  57. Matthias Neeracher                                   neeri@iis.ethz.ch
  58.    "One fine day in my odd past..." -- Pixies, _Planet of Sound_
  59.