home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #16 / NN_1992_16.iso / spool / comp / programm / 2040 < prev    next >
Encoding:
Text File  |  1992-07-21  |  2.0 KB  |  52 lines
  1. Newsgroups: comp.programming
  2. Path: sparky!uunet!newsgate.watson.ibm.com!yktnews!admin!flu!lowry
  3. From: lowry@watson.ibm.com (Andy Lowry)
  4. Subject: Re: finding 1st one in integer
  5. Sender: news@watson.ibm.com (NNTP News Poster)
  6. Message-ID: <LOWRY.92Jul21165844@rotor.watson.ibm.com>
  7. In-Reply-To: amichail@cayley.waterloo.edu's message of Tue, 21 Jul 1992 14:40:26 GMT
  8. Date: Tue, 21 Jul 1992 21:58:44 GMT
  9. Disclaimer: This posting represents the poster's views, not necessarily those of IBM
  10. References: <Brqu3F.1J4@undergrad.math.waterloo.edu>
  11. Nntp-Posting-Host: rotor.watson.ibm.com
  12. Organization: IBM T.J. Watson Research Center
  13. Lines: 37
  14.  
  15. In article <Brqu3F.1J4@undergrad.math.waterloo.edu> amichail@cayley.waterloo.edu (Amir Michail) writes:
  16.  
  17.  > I need a very efficient way of finding the first bit set ( doesn't matter
  18.  > which side ) in a 32 bit integer. 
  19.  
  20.  > One can make the simplifying assumption that only 1 bit will be
  21.  > set in the 32 bit integer (if that helps).
  22.  
  23. This seems to work nicely:
  24.  
  25. int firstone(x)
  26. unsigned int x;
  27. {
  28.   static int keys[] = {
  29.     -1,  0,  1, 26,  2, 23, 27, -1,  3, 16,
  30.     24, 30, 28, 11, -1, 13,  4,  7, 17, -1,
  31.     25, 22, 31, 15, 29, 10, 12,  6, -1, 21,
  32.     14,  9,  5, 20,  8, 19, 18 };
  33.  
  34.   return keys[x % 37];
  35. }
  36.  
  37. The idea is that you want to use a table lookup, but not on the entire
  38. sparse range 1-2^31, so you need to find a hash function that will map
  39. the set {2^n: 0 <= n <= 31} uniquely to a reasonably dense range of
  40. integers.  Using remainder modulo 37 does the trick, and the table
  41. above was generated by a trivial C program.  The -1 entries are
  42. unused.
  43.  
  44. There's probably some algebraic way of predicting what divisor to use
  45. instead of 37 to get the minimum sized table for a given "word size,"
  46. but I'll leave that for somebody else to fill in.  I just started with
  47. 33 and tried successive numbers until one worked.  But I don't believe
  48. it can be a coincidence that 37 is the least prime greater than 32!
  49. --
  50. Andy Lowry, lowry@watson.ibm.com, (914) 784-7925
  51. IBM Research, P.O. Box 704, Yorktown Heights, NY  10598
  52.