home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #16 / NN_1992_16.iso / spool / comp / programm / 2036 < prev    next >
Encoding:
Text File  |  1992-07-21  |  1.1 KB  |  36 lines
  1. Newsgroups: comp.programming
  2. Path: sparky!uunet!zaphod.mps.ohio-state.edu!rpi!batcomputer!cornell!ressler
  3. From: ressler@cs.cornell.edu (Gene Ressler)
  4. Subject: Re: finding 1st one in integer
  5. Message-ID: <1992Jul21.194749.25918@cs.cornell.edu>
  6. Organization: Cornell Univ. CS Dept, Ithaca NY 14853
  7. References: <Brqu3F.1J4@undergrad.math.waterloo.edu>
  8. Date: Tue, 21 Jul 1992 19:47:49 GMT
  9. Lines: 25
  10.  
  11. In article <Brqu3F.1J4@undergrad.math.waterloo.edu> amichail@cayley.waterloo.edu (Amir Michail) writes:
  12. >I need a very efficient way of finding the first bit set ( doesn't matter
  13. >which side ) in a 32 bit integer. 
  14. >
  15. >For example:
  16. >
  17. >  binary  -> position
  18. >      1 -> 0
  19. >    10000 -> 4
  20. >     1000 -> 3
  21.  
  22. If `doesn't matter which side' means it's acceptable to find the
  23. position of the _least_ significant bit set, then a solution
  24. that's good on 2's complement machines is:
  25.  
  26.     n = (n & -n) - 1;
  27.     /* return the # 1's in n */
  28.  
  29. You can count the number of 1's in n with any of the amazing
  30. methods suggested in recent posts.   This works because
  31. in 2's complement, n & -n is the least significant 1 bit of
  32. n.  Subtracting 1 turns it into a string of 1's beneath
  33. the ls1b.
  34.  
  35. Gene
  36.