home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #16 / NN_1992_16.iso / spool / comp / programm / 2057 < prev    next >
Encoding:
Text File  |  1992-07-22  |  1.8 KB  |  49 lines
  1. Newsgroups: comp.programming
  2. Path: sparky!uunet!caen!batcomputer!cornell!ressler
  3. From: ressler@cs.cornell.edu (Gene Ressler)
  4. Subject: Re: finding 1st one in integer
  5. Message-ID: <1992Jul22.152827.14267@cs.cornell.edu>
  6. Organization: Cornell Univ. CS Dept, Ithaca NY 14853
  7. References: <Brqu3F.1J4@undergrad.math.waterloo.edu> <LOWRY.92Jul21165844@rotor.watson.ibm.com> <BrsMBE.98t@undergrad.math.waterloo.edu>
  8. Date: Wed, 22 Jul 1992 15:28:27 GMT
  9. Lines: 38
  10.  
  11. In article <BrsMBE.98t@undergrad.math.waterloo.edu> amichail@cayley.waterloo.edu (Amir Michail) writes:
  12. >In article <LOWRY.92Jul21165844@rotor.watson.ibm.com>, lowry@watson.ibm.com (Andy Lowry) writes:
  13. >>   return keys[x % 37];
  14. >
  15. >Yes, I thought of this method initially.  The only problem is that the
  16. >modulus operation is *VERY* slow on some architectures such as the sparc.
  17.  
  18. Right.  This is why I proposed counting 1's.  If you assume 2s complement and
  19. that n has exactly one 1, then just decrement and count.  From the nice posted
  20. benchmark code (chris torek?), this runs about 400% faster than the 37 element
  21. table lookup on a Sparc:
  22.  
  23. int position_of_1(n)
  24. register unsigned long n;
  25. {
  26.     --n;  /* Replace with n=(n&-n)-1 to find pos of ls1b in any number. */
  27.     n = (n & 0x55555555) + ((n >> 1) & 0x55555555);
  28.     n = (n & 0x33333333) + ((n >> 2) & 0x33333333);
  29.     n = (n + (n >> 4)) & 0x0f0f0f0f;
  30.     n += n >> 8;
  31.     n += n >> 16;
  32.     return (n & 0xff);
  33. }
  34.  
  35. Even without slow %, this seems better than tables because table 
  36. accesses can cause cache misses.
  37.  
  38. Murphey's 1st law of caches:
  39. With an n-way set-associative cach, you'll have n+1 conflicting 
  40. accesses in the inner loop.
  41.  
  42. Murphey's 2nd law of caches:
  43. Murphey's 1st law doesn't apply to timing benchmarks.
  44.  
  45. It also promises better instruction schedules than vadim's jumping
  46. code. Is it faster?  I haven't tried it.
  47.  
  48. Gene
  49.