home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #16 / NN_1992_16.iso / spool / comp / programm / 2035 < prev    next >
Encoding:
Text File  |  1992-07-21  |  2.3 KB  |  66 lines
  1. Newsgroups: comp.programming
  2. Path: sparky!uunet!s5!is1.is.morgan.com!is.morgan.com!berlin
  3. From: berlin@is.morgan.com (Alexander Berlin)
  4. Subject: Re: finding 1st one in integer
  5. Message-ID: <1992Jul21.150033@is.morgan.com>
  6. Sender: news@is.morgan.com
  7. Nntp-Posting-Host: chico
  8. Organization: Morgan Stanley - IS
  9. References: <Brqu3F.1J4@undergrad.math.waterloo.edu>  <1992Jul21.173805.12045@bcrka451.bnr.ca>
  10. Date: Tue, 21 Jul 1992 19:00:33 GMT
  11. Lines: 53
  12.  
  13. In article <1992Jul21.173805.12045@bcrka451.bnr.ca>, sjm@bcrki65.bnr.ca (Stuart MacMartin) writes:
  14. |> In article <Brqu3F.1J4@undergrad.math.waterloo.edu>,
  15. |> amichail@cayley.waterloo.edu (Amir Michail) writes:
  16. |> > I need a very efficient way of finding the first bit set ( doesn't matter
  17. |> > which side ) in a 32 bit integer. 
  18. |> > 
  19. |> > For example:
  20. |> > 
  21. |> >   binary  -> position
  22. |> >       1 -> 0
  23. |> >     10000 -> 4
  24. |> >      1000 -> 3
  25. |> > 
  26. |> > One can make the simplifying assumption that only 1 bit will be
  27. |> > set in the 32 bit integer (if that helps).
  28. |> > 
  29. |> > Amir
  30. |> > 
  31. |> > P.S.  Please do not tell me to use a large lookup table.  I know about that.
  32. |> >       I also know that the 68020 and 80386 have instructions to do
  33. |> this; I want
  34. |> >       portable C code though.
  35. |> 
  36. |> Check a byte at a time for non-zero (being careful not to assume byte
  37. |> ordering or behaviour of shifting signed values if you want to be portable).
  38. |> 
  39. |> Either use a lookup table of 256 values, or split the byte into two
  40. |> so that your table is only 16 long.
  41. |> 
  42. |> If you often have numbers with the 2 lowest bytes clear, you might want to
  43. |> start by checking 2-byte values against 0.
  44. |> 
  45. |> Stuart
  46. |> 
  47. |> : Stuart MacMartin                                    email: sjm@bnr.ca      :
  48. |> : Bell-Northern Research                              phone: (613) 763-5625  :
  49. |> : PO Box 3511, Stn C, Ottawa, K1Y-4H7, CANADA    Standard disclaimers apply. :
  50.  
  51. how about this one line solution:
  52.  
  53. unsigned int i;  /* given integer */
  54. unsigned int j;  /* working variable */
  55. int          bitset;  /* result */
  56.  
  57.    for(j=1, bitset=1; ; bitset++, j+=j) if (i==j) break; /* sets bitset */
  58.  
  59. Will work, of course, only when exactly one bit is set. But you want
  60. efficiency, so there is no unnecessary conditions. And it looks portable -
  61. doesn't even rely on the int size. 
  62.  
  63. ---
  64. Alex Berlin                     
  65. berlin@is.morgan.com
  66.