home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #16 / NN_1992_16.iso / spool / comp / programm / 2034 < prev    next >
Encoding:
Text File  |  1992-07-21  |  1.7 KB  |  49 lines
  1. Newsgroups: comp.programming
  2. Path: sparky!uunet!europa.asd.contel.com!darwin.sura.net!convex!news.utdallas.edu!corpgate!bnrgate!bcrka451!bcrki65!sjm
  3. From: sjm@bcrki65.bnr.ca (Stuart MacMartin)
  4. Subject: Re: finding 1st one in integer
  5. Message-ID: <1992Jul21.173805.12045@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: <Brqu3F.1J4@undergrad.math.waterloo.edu> 
  10. Date: Tue, 21 Jul 1992 17:38:05 GMT
  11. Lines: 36
  12.  
  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. > For example:
  19. > 
  20. >   binary  -> position
  21. >       1 -> 0
  22. >     10000 -> 4
  23. >      1000 -> 3
  24. > 
  25. > One can make the simplifying assumption that only 1 bit will be
  26. > set in the 32 bit integer (if that helps).
  27. > 
  28. > Amir
  29. > 
  30. > P.S.  Please do not tell me to use a large lookup table.  I know about that.
  31. >       I also know that the 68020 and 80386 have instructions to do
  32. this; I want
  33. >       portable C code though.
  34.  
  35. Check a byte at a time for non-zero (being careful not to assume byte
  36. ordering or behaviour of shifting signed values if you want to be portable).
  37.  
  38. Either use a lookup table of 256 values, or split the byte into two
  39. so that your table is only 16 long.
  40.  
  41. If you often have numbers with the 2 lowest bytes clear, you might want to
  42. start by checking 2-byte values against 0.
  43.  
  44. Stuart
  45.  
  46. : Stuart MacMartin                                    email: sjm@bnr.ca      :
  47. : Bell-Northern Research                              phone: (613) 763-5625  :
  48. : PO Box 3511, Stn C, Ottawa, K1Y-4H7, CANADA    Standard disclaimers apply. :
  49.