home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #16 / NN_1992_16.iso / spool / comp / programm / 2056 < prev    next >
Encoding:
Text File  |  1992-07-22  |  2.3 KB  |  59 lines
  1. Newsgroups: comp.programming
  2. Path: sparky!uunet!utcsri!torn!cunews!nrcnet0!bnrgate!bcrka451!bcrki65!sjm
  3. From: sjm@bcrki65.bnr.ca (Stuart MacMartin)
  4. Subject: Re: finding 1st one in integer
  5. Message-ID: <1992Jul22.140938.27938@bcrka451.bnr.ca>
  6. Sender: 5E00 Corkstown News Server
  7. Reply-To: sjm@bcrki65.bnr.ca (Stuart MacMartin)
  8. Organization: Bell-Northern Research, Ottawa, Canada
  9. References: <LOWRY.92Jul21165844@rotor.watson.ibm.com> <Brqu3F.1J4@undergrad.math.waterloo.edu>
  10. Date: Wed, 22 Jul 1992 14:09:38 GMT
  11. Lines: 46
  12.  
  13. In article <LOWRY.92Jul21165844@rotor.watson.ibm.com>,
  14. lowry@watson.ibm.com (Andy Lowry) writes:
  15. > In article <Brqu3F.1J4@undergrad.math.waterloo.edu>
  16. amichail@cayley.waterloo.edu (Amir Michail) writes:
  17. > 
  18. >  > I need a very efficient way of finding the first bit set ( doesn't matter
  19. >  > which side ) in a 32 bit integer. 
  20. > 
  21. >  > One can make the simplifying assumption that only 1 bit will be
  22. >  > set in the 32 bit integer (if that helps).
  23. > 
  24. > This seems to work nicely:
  25. > 
  26. > int firstone(x)
  27. > unsigned int x;
  28. > {
  29. >   static int keys[] = {
  30. >     -1,  0,  1, 26,  2, 23, 27, -1,  3, 16,
  31. >     24, 30, 28, 11, -1, 13,  4,  7, 17, -1,
  32. >     25, 22, 31, 15, 29, 10, 12,  6, -1, 21,
  33. >     14,  9,  5, 20,  8, 19, 18 };
  34. > 
  35. >   return keys[x % 37];
  36. > }
  37. > 
  38.  
  39. Very nice.  
  40.  
  41. The difference between this and the one I (and another) suggested
  42. is that this one relies on only one bit being set, whereas my solution was
  43. more general and did not use the simplifying assumption.  This one ought to
  44. be faster, although the % is slow on some machines.  So the choice really 
  45. comes down to:  do you want to make the simplifying assumption, or are you
  46. going to want to use the same routine later in a case that has more than
  47. one bit set?  This example is so trivial that you would implement both when
  48. needed, but sometimes it is better to write routines slightly more general
  49. than you need if this does not make a *noticeable* difference in performance.
  50.  
  51. About >>=:   Yes this is portable *if* the value is unsigned.  If the value
  52. is signed, then this might do either logical or arithmetic shifting.
  53.  
  54. Stuart
  55.  
  56. : Stuart MacMartin                                    email: sjm@bnr.ca      :
  57. : Bell-Northern Research                              phone: (613) 763-5625  :
  58. : PO Box 3511, Stn C, Ottawa, K1Y-4H7, CANADA    Standard disclaimers apply. :
  59.