home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1993 #1 / NN_1993_1.iso / spool / comp / sys / mac / programm / 21087 < prev    next >
Encoding:
Text File  |  1993-01-09  |  1.7 KB  |  37 lines
  1. Newsgroups: comp.sys.mac.programmer
  2. Path: sparky!uunet!zaphod.mps.ohio-state.edu!uwm.edu!ux1.cso.uiuc.edu!news.cs.indiana.edu!umn.edu!csus.edu!netcom.com!norm
  3. From: norm@netcom.com (Norman Hardy)
  4. Subject: Re: (Q) Need bit manipulation algorithm
  5. Message-ID: <1993Jan9.212559.5319@netcom.com>
  6. Organization: Netcom Online Communications Services (408-241-9760 login: guest)
  7. References: <1993Jan6.022430.19469@leland.Stanford.EDU> <1993Jan6.032113.597@planets.risc.rockwell.com> <20751@ucdavis.ucdavis.edu>
  8. Date: Sat, 9 Jan 1993 21:25:59 GMT
  9. Lines: 26
  10.  
  11. In article <20751@ucdavis.ucdavis.edu> lim@toadflax.cs.ucdavis.edu (Lloyd Lim) writes:
  12. >
  13. >There is a neat trick for counting the number of bits in a word that
  14. >a Microsoft geek showed me one time.  If there are k bits with 1's,
  15. >it runs in O(k) time.
  16. >
  17. >I don't remember the algorithm, but it involved subtracting 1 and could
  18. >be written in one line of C.  (Yeah, I know...  You could write anything,
  19. >even Microsoft Word, in one very long line of C code.  Come to think of it,
  20. >that's probably what they did.)  The subtraction was used to create
  21. >instant masks: e.g. 0x0100 - 1 = 0x00FF.  It went from the highest 1 bit
  22. >to the lowest, magically avoiding all of the 0's.
  23. >
  24. >That's all I remember.  Anyone remember this algorithm?
  25. >
  26. >+++
  27. >Lloyd Lim                    Internet: lim@cs.ucdavis.edu
  28. >Lim Unlimited                America Online: LimUnltd
  29. >330 W. Iris Ave.             AppleLink: LimUnltd
  30. >Stockton, CA  95210-3738     CompuServe: 72647,660
  31. There are several versions much like the following:
  32.  
  33. #include <stdio.h>
  34. int main(){int K; for(K=-4; K<15; ++K) 
  35.   {int j=0, k=K; while(k) {k = k-1 & k; ++j;}
  36.     printf("There are %d ones in %d.\n", j, K);}}
  37.