home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1993 #1 / NN_1993_1.iso / spool / comp / sys / mac / programm / 20775 < prev    next >
Encoding:
Internet Message Format  |  1993-01-06  |  1.8 KB
  1. Path: sparky!uunet!paladin.american.edu!howland.reston.ans.net!zaphod.mps.ohio-state.edu!cis.ohio-state.edu!ucbvax!ucdavis!toadflax!lim
  2. From: lim@toadflax.cs.ucdavis.edu (Lloyd Lim)
  3. Newsgroups: comp.sys.mac.programmer
  4. Subject: Re: (Q) Need bit manipulation algorithm
  5. Summary: bit counting and gratuitous Microsoft bashing
  6. Message-ID: <20751@ucdavis.ucdavis.edu>
  7. Date: 6 Jan 93 10:19:11 GMT
  8. References: <1993Jan6.022430.19469@leland.Stanford.EDU> <1993Jan6.032113.597@planets.risc.rockwell.com>
  9. Sender: usenet@ucdavis.ucdavis.edu
  10. Organization: Department of Computer Science, University of California, Davis
  11. Lines: 26
  12.  
  13. In article <1993Jan6.032113.597@planets.risc.rockwell.com> sho@risc.rockwell.com (Sho Kuwamoto) writes:
  14. >
  15. >Maybe not the fastest method, but a simple one:
  16. >   1) come up with an algorithm which counts the number of
  17. >      1's in a given bit pattern.  You'll either use a loop
  18. >      with shifts and increments in it, or you'll use masks.
  19. >[...]
  20.  
  21. There is a neat trick for counting the number of bits in a word that
  22. a Microsoft geek showed me one time.  If there are k bits with 1's,
  23. it runs in O(k) time.
  24.  
  25. I don't remember the algorithm, but it involved subtracting 1 and could
  26. be written in one line of C.  (Yeah, I know...  You could write anything,
  27. even Microsoft Word, in one very long line of C code.  Come to think of it,
  28. that's probably what they did.)  The subtraction was used to create
  29. instant masks: e.g. 0x0100 - 1 = 0x00FF.  It went from the highest 1 bit
  30. to the lowest, magically avoiding all of the 0's.
  31.  
  32. That's all I remember.  Anyone remember this algorithm?
  33.  
  34. +++
  35. Lloyd Lim                    Internet: lim@cs.ucdavis.edu
  36. Lim Unlimited                America Online: LimUnltd
  37. 330 W. Iris Ave.             AppleLink: LimUnltd
  38. Stockton, CA  95210-3738     CompuServe: 72647,660
  39.