home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1993 #1 / NN_1993_1.iso / spool / comp / sys / mac / programm / 20761 < prev    next >
Encoding:
Internet Message Format  |  1993-01-06  |  1.8 KB
  1. Path: sparky!uunet!cis.ohio-state.edu!zaphod.mps.ohio-state.edu!swrinde!emory!ogicse!reed!bowman
  2. From: bowman@reed.edu (BoBolicious)
  3. Newsgroups: comp.sys.mac.programmer
  4. Subject: Re: (Q) Need bit manipulation algorithm
  5. Message-ID: <1993Jan6.040823.23901@reed.edu>
  6. Date: 6 Jan 93 04:08:23 GMT
  7. Article-I.D.: reed.1993Jan6.040823.23901
  8. References: <1993Jan6.022430.19469@leland.Stanford.EDU>
  9. Organization: Reed College, Portland, OR
  10. Lines: 24
  11.  
  12. In article <1993Jan6.022430.19469@leland.Stanford.EDU> felciano@summit.stanford.edu (Ramon M. Felciano) writes:
  13. >I've got an interesting bit-manipulation problem for you. I need to
  14. >know how to match a given bit pattern into a stored array of patterns.
  15. >In particular, I need to come up with a "fuzzy match" if no exact one
  16. >is found.
  17.  
  18. The best way I can see to do this is to XOR your test pattern with each member
  19. of the table.  Then the number of "on" bits (the Hamming distance?) is the
  20. number of bits by which the two patterns differ.  I don't know the most
  21. efficient way to count the number of "on" bits; there are several ways to
  22. do it, so if you need it to be super-fast, you might want to experiment between
  23. looping through each bit in the pattern, shifting each time and testing the
  24. lowest (or highest, depending on which way you shift) bit.  Or you could 
  25. maintain a table which contained 1,2,4,8,16,... and AND the result of each
  26. XOR with each member of *this* table.
  27.  
  28. Doing the actual bookkeeping to keep track of which one(s) to return and
  29. by how many bits they differ from the test pattern should be pretty trivial.
  30.  
  31. cheers,
  32. bobo              In seeking the unattainable,
  33. bowman@reed.edu            simplicity only gets in the way.
  34. "On Monday, numbers floated everywhere, and the world was full of 
  35. approximations."  -- Spencer Heinz, _The Oregonian_, 1/5/93
  36.