home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #16 / NN_1992_16.iso / spool / comp / programm / 2065 < prev    next >
Encoding:
Internet Message Format  |  1992-07-22  |  2.6 KB
  1. Path: sparky!uunet!usc!zaphod.mps.ohio-state.edu!uakari.primate.wisc.edu!ames!think.com!unixland!public!peterk
  2. From: peterk@public.sub.org (Peter Kittel)
  3. Newsgroups: comp.programming
  4. Subject: Re: finding 1st one in integer
  5. Message-ID: <1992Jul22.121859.12676@public.sub.org>
  6. Date: 22 Jul 92 12:18:59 GMT
  7. References: <Brqu3F.1J4@undergrad.math.waterloo.edu>  <1992Jul21.173805.12045@bcrka451.bnr.ca> <1992Jul21.150033@is.morgan.com>
  8. Organization: Public News & Mailserver, Commodore Germany PM UNIX, Frankfurt
  9. Lines: 56
  10.  
  11. berlin@is.morgan.com (Alexander Berlin) writes:
  12. >In article <1992Jul21.173805.12045@bcrka451.bnr.ca>, sjm@bcrki65.bnr.ca (Stuart MacMartin) writes:
  13. >|> In article <Brqu3F.1J4@undergrad.math.waterloo.edu>,
  14. >|> amichail@cayley.waterloo.edu (Amir Michail) writes:
  15. >|> > I need a very efficient way of finding the first bit set ( doesn't matter
  16. >|> > which side ) in a 32 bit integer. 
  17. >|> > 
  18. >|> >   binary  -> position
  19. >|> >       1 -> 0
  20. >|> >     10000 -> 4
  21. >|> >      1000 -> 3
  22. >|> > 
  23. >|> > One can make the simplifying assumption that only 1 bit will be
  24. >|> > set in the 32 bit integer (if that helps).
  25. >|> 
  26. >|> Check a byte at a time for non-zero (being careful not to assume byte
  27. >|> ordering or behaviour of shifting signed values if you want to be portable).
  28.  
  29. Sounds like a good advice. This makes 4 comparisons in the outer loop.
  30.  
  31. >|> Either use a lookup table of 256 values, or split the byte into two
  32. >|> so that your table is only 16 long.
  33.  
  34. Why tables? We *have* bit operators in C!
  35.  
  36. >|> If you often have numbers with the 2 lowest bytes clear, you might want to
  37. >|> start by checking 2-byte values against 0.
  38.  
  39. Or even simpler, as very first action, compare with 65536.
  40.  
  41. >how about this one line solution:
  42.  
  43. It's a bit slow, I fear, he asked for an *efficient* way.
  44.  
  45. >unsigned int i;  /* given integer */
  46. >unsigned int j;  /* working variable */
  47. >int          bitset;  /* result */
  48.  
  49. >   for(j=1, bitset=1; ; bitset++, j+=j) if (i==j) break; /* sets bitset */
  50.  
  51. And you run the loop from the wrong side, he searches the first bit from
  52. left! So how about this:
  53.  
  54. if (i>65535)  /* upper or lower 16 bits? */
  55.   { for (bitset=31; bitset>15; bitset--) if (i & (1<<bitset)) break; }
  56.       else
  57.   { for (bitset=15; bitset>=0; bitset--) if (i & (1<<bitset)) break; }
  58.  
  59. For gaining even more speed you could do more outer if's for bytes and
  60. nibbles and so on, building a binary tree (but can't imagine a simple
  61. loop statement to do this sort of binary search).
  62.  
  63. -- 
  64. Best regards, Dr. Peter Kittel  // E-Mail to  \\  Only my personal opinions... 
  65. Commodore Frankfurt, Germany  \X/ {uunet|pyramid|rutgers}!cbmvax!cbmger!peterk
  66.                                    or  peterk@public.sub.org
  67.