home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1993 #1 / NN_1993_1.iso / spool / comp / sys / mac / programm / 20760 < prev    next >
Encoding:
Text File  |  1993-01-06  |  1.4 KB  |  37 lines
  1. Newsgroups: comp.sys.mac.programmer
  2. Path: sparky!uunet!stanford.edu!rpal.rockwell.com!planets!sho
  3. From: sho@planets.risc.rockwell.com (Sho Kuwamoto)
  4. Subject: Re: (Q) Need bit manipulation algorithm
  5. Message-ID: <1993Jan6.032113.597@planets.risc.rockwell.com>
  6. Reply-To: sho@risc.rockwell.com (Sho Kuwamoto)
  7. Organization: Rockwell International Science Center, Thousand Oaks, Ca.
  8. References: <1993Jan6.022430.19469@leland.Stanford.EDU>
  9. Date: Wed, 6 Jan 93 03:21:13 GMT
  10. Lines: 25
  11.  
  12. In article <1993Jan6.022430.19469@leland.Stanford.EDU> felciano@summit.stanford.edu (Ramon M. Felciano) writes:
  13. >So: I need an algorithm that will find a consistent fuzzy match by
  14. >subtracting bits. It needs to deal with ambiguities like #9 and #10.
  15. >Thus if two matches have 90% of the bits in common, I need both of
  16. >them back, one after the other (the order doesn't matter).
  17.  
  18. Maybe not the fastest method, but a simple one:
  19.    1) come up with an algorithm which counts the number of
  20.       1's in a given bit pattern.  You'll either use a loop
  21.       with shifts and increments in it, or you'll use masks.
  22.  
  23.    for each pattern, 
  24.      2) bitwise xor your input with the pattern.
  25.      3) count the number of 1's which result.
  26.  
  27.    4) return those patterns which yield the smallest sums.
  28.  
  29. Remember that for step 3, you can stop counting when the
  30. number of 1's exceeds that of the optimal pattern
  31. encountered up to that point.
  32.  
  33. -Sho
  34. --
  35. sho@physics.purdue.edu
  36. sho@risc.rockwell.com
  37.