home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #16 / NN_1992_16.iso / spool / comp / lang / cplus / 11329 < prev    next >
Encoding:
Internet Message Format  |  1992-07-22  |  1.1 KB
  1. Xref: sparky comp.lang.c++:11329 comp.lang.c:11438
  2. Newsgroups: comp.lang.c++,comp.lang.c
  3. Path: sparky!uunet!zaphod.mps.ohio-state.edu!wupost!m.cs.uiuc.edu!kale
  4. From: kale@m.cs.uiuc.edu (L. V. Kale')
  5. Subject: Re: Population count.
  6. Message-ID: <1992Jul22.170132.29418@m.cs.uiuc.edu>
  7. Organization: University of Illinois, Dept. of Comp. Sci., Urbana, IL
  8. References: <1992Jul14.133241.23637@ncsu.edu> <Bro0u3.4y0@watserv1.waterloo.edu> <1992Jul20.070613.23553@klaava.Helsinki.FI>
  9. Date: Wed, 22 Jul 1992 17:01:32 GMT
  10. Lines: 24
  11.  
  12.  
  13. Here is a simple code-fragement that counts the number of 1's in
  14. a word stored in x.
  15.  
  16. int x, count;
  17. ...
  18. count = 0;
  19. while (x) { count++; x = x & (x-1); }
  20.  
  21. Nice things about this: uses only two variable which can be expected to be in
  22. registers (unlike the lookup table).
  23. Also, loops only as many times as the number of ones. This is good
  24. for words with very few ones.
  25.  
  26. The algorithm was taken from "Combinatorial Algorithms" book, by 
  27. Reingold, Nievergelt and Deo.
  28. I used this in a primes-sieve program for counting the number of primes
  29. in a bitvector.
  30.  
  31. -- 
  32.  
  33. kale@cs.uiuc.edu
  34. L.V. Kale
  35. Dept. of Computer Science
  36.