home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1993 #1 / NN_1993_1.iso / spool / comp / sys / mac / programm / 21217 < prev    next >
Encoding:
Text File  |  1993-01-11  |  1.5 KB  |  38 lines
  1. Newsgroups: comp.sys.mac.programmer
  2. Path: sparky!uunet!mcsun!sunic!kth.se!byse.nada.kth.se!d88-jwa
  3. From: d88-jwa@byse.nada.kth.se (Jon WΣtte)
  4. Subject: Re: (Q) Need bit manipulation algorithm
  5. Message-ID: <1993Jan11.222234.27054@kth.se>
  6. Sender: usenet@kth.se (Usenet)
  7. Nntp-Posting-Host: byse.nada.kth.se
  8. Organization: Royal Institute of Technology, Stockholm, Sweden
  9. References: <1993Jan6.022430.19469@leland.Stanford.EDU> <NEERI.93Jan6143512@iis.ethz.ch> <1if329INN2f0@falcon.natinst.com> <1993Jan08.012806.14863@eng.umd.edu> <34440@goofy.apple.COM>
  10. Date: Mon, 11 Jan 1993 22:22:34 GMT
  11. Lines: 25
  12.  
  13. In <34440@goofy.apple.COM> chris_russo@gateway.qm.apple.com (Christopher Russo) writes:
  14.  
  15. >>>There is a neat trick for counting the number of bits in a word that
  16. >>>a Microsoft geek showed me one time.  If there are k bits with 1's,
  17. >>>it runs in O(k) time.
  18.  
  19. >I learned a cool way in an interview here at Apple.  For the number of 
  20. >bits in a byte, all you'd need is a 256 byte look-up table where the 
  21. >index designated by, say, 00001010 would be index $A into the table which 
  22. >would contain the number 2 (that you put there.)  It's pretty fast.
  23.  
  24. Yes, but it runs in O(b) time, where b is the number of bits
  25. (i.e. one table lookup for each byte in the word) It's not even
  26. a neat trick; it's one of those friggin obvious things that
  27. someone probably patented :-)
  28.  
  29. I still want to know the O(number-of-bits-set) algorithm.
  30.  
  31. Cheers,
  32.  
  33.                         / h+
  34. -- 
  35.  -- Jon W{tte, h+@nada.kth.se, Mac Hacker Deluxe --
  36.    This signature is kept shorter than 4 lines in the interests of UseNet
  37.    S/N ratio.
  38.