counting matching bits / bitXnor

nicolas cellier ncellier at ifrance.com
Tue Dec 18 01:33:05 UTC 2007


Cees de Groot a écrit :
> Hi,
> 
> I'm fiddling with some little project where I need to count the number
> of bits that are the same between two bitstrings. My first
> approximation would be to bitXnor: both integers and count bits in the
> result. However, there's no bitXnor: and the standard implementation:
> 
> a XNOR b = (a AND b) OR (NOT a AND NOT b)
> 
> won't fly because there's not bitNot in Integer, as far as I can tell
> (negate draws in all the ugliness of 2-complement arithmetic :)).
> 
> It's probably a stupid question that only shows how rusty my bit
> fiddling is - but what would be a *good* performing implementation of
> something that counts matching bits? (for extra credits: if the two
> integers are unequal in size, it's a pattern match so the smaller int
> needs to be shifted along the larger int and the largest count is the
> one that's returned):
> 
> 011101 / 101 -> 3
> 011111 / 101 -> 2
> 0101 / 0001 -> 3
> ... etcetera)
> 

I don't understand how you could achieve that with Integer

0101 / 0001 -> 3
00101 / 00001 -> 4
000101 / 000001 -> 5

Same integer, different results...

So yes, BitArray as suggested by Yoshiki is maybe your option

Nicolas




More information about the Squeak-dev mailing list