On Dec 17, 2007 1:34 PM, Paolo Bonzini <bonzini at gnu.org> wrote:
> There's bitInvert, I think (I have no Squeak image here).  If you don't
> have it, bitInvert is just "-1 - self".
>
Yup - and that draws in a sign and other ugliness. At least, in a
direct implementation of bitXnor:

bitXnor: anInteger
	" return bit-wise XNOR of two numbers. "
	
	^ (self bitAnd: anInteger) bitOr: (self bitInvert bitAnd: anInteger bitInvert)

0 bitXnor: 0 -> -1

> You need to give the width, as (if both numbers have the same sign, at
> least) you can always add a zero to the left and get one more matching
> bit. :-)   So the method would be something like this:
>
>       bitMatch: b width: n
>           ^((self bitXor: b) bitInvert bitAnd: (1 bitShift: n) - 1)
>               bitCount
>
>       bitCount
>           | n cnt |
>           n := self. cnt := 0.
>           [ n = 0 ] whileFalse: [
>               cnt := cnt + 1.
>               n := n bitAnd: n - 1 ].
>           ^cnt
>
> I don't know the answer for this, but I know of an efficient algorithm
> for a similar problem, that is to *find* a bitstring in another.  For
> this, you can adapt the Knuth-Morris-Pratt string searching algorithm.
>
Yeah, but that's for exact searching... besides, I feel that if I can
get the bitcounting efficient the couple of loop/shift operations
needed to shift the shorter pattern along the larger one should be ok.

Thanks for the suggested implementation - i'll throw it at my unit tests :-)

(if you think - wth is that guy needing that stuff for - the bit
strings are genomes, and i want to make some decisions in an
artificial life algorithm based on 'fit' - how well the genomes match
(and also on 'non-fit' - how far they are apart, but that is step 2).
Just something to keep me busy in the train commute)

-- 
"Human beings make life so interesting. Do you know, that in a
universe so full of wonders, they have managed to invent boredom. " -
Death, in "The Hogfather"