Re: scoring differences between bitmasks

On Sat, Oct 01, 2005 at 07:12:13PM -0700, Ben wrote:
> I'm looking for a quick way to find the number of bits that are
> different between two bitmasks of the same size. I'll be doing this a
> lot, so speed is desirable.... some kind of indexing would be even
> better. It seems like this problem must have been solved before....

Step 1: Use XOR to get the bits that are different.
Step 2: Count the bits.

Something like x & ((~x) +1) will give you the value of the last
bit that is set, mask it out and repeat. If you need to do it a lot,
build a table of 256 values and then process 8 bits at a time. Should
be fairly straight forward...

Hope this helps,
--
Martijn van Oosterhout <kleptog(at)svana(dot)org> http://svana.org/kleptog/
> Patent. n. Genius is 5% inspiration and 95% perspiration. A patent is a
> tool for doing 5% of the work and then sitting around waiting for someone
> else to do the other 95% so you can sue them.