home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #16 / NN_1992_16.iso / spool / comp / programm / 2046 < prev    next >
Encoding:
Internet Message Format  |  1992-07-21  |  1.6 KB
  1. Path: sparky!uunet!iWarp.intel.com|inews!pinkas
  2. From: pinkas@caraway.intel.com (Israel Pinkas)
  3. Newsgroups: comp.programming
  4. Subject: Re: finding 1st one in integer
  5. Message-ID: <PINKAS.92Jul21181341@caraway.intel.com>
  6. Date: 22 Jul 92 01:13:41 GMT
  7. References: <Brqu3F.1J4@undergrad.math.waterloo.edu>
  8.     <1992Jul21.173805.12045@bcrka451.bnr.ca>
  9.     <1992Jul21.150033@is.morgan.com> <1992Jul21.205127.23216@wdl.loral.com>
  10. Sender: news@inews.intel.com
  11. Organization: Software Technologies, INTeL Corporation, Santa Clara, CA
  12. Lines: 27
  13. In-reply-to: mab@wdl39.wdl.loral.com's message of 21 Jul 92 20:51:27 GMT
  14.  
  15. mab@wdl39.wdl.loral.com (Mark A Biggar) writes:
  16.  
  17.    This is no problem as i^(i-1) produces a value consisting on just the least
  18.    sigfinicant bit in i
  19.  
  20. Not quite.  i-1 zeros the lease significant bit of i, but it sets all the
  21. lower bits.  Exclusive ORing with i zeros all but the least significant 1
  22. bit, but it sets all the lower bits.
  23.  
  24. (i^(i-1))>>1+1 should do the trick for all values of i.  i should be
  25. defined as an unsigned entity to avoid problems.  Constant time, four
  26. operations.
  27.  
  28.     i    i-1    i^(i-1)    (i^(i-1))>>1    (i^(i-1))>>1+1
  29.     ------------------------------------------------------
  30.     000001    000000    000001    000000        000001
  31.     000010    000001    000010    000001        000010
  32.     000011    000010    000001    000000        000001
  33. Note    000110    000101    000011    000001        000010
  34.     101100    101011    000111    000011        000100
  35.     101010    101001    000011    000001        000010
  36.  
  37. -Israel
  38. --
  39. Disclaimer: The above are my personal opinions, and in no way represent
  40. the opinions of Intel Corporation.  In no way should the above be taken
  41. to be a statement of Intel.
  42.