Re: [eigen] Vectorized Hamming distance

[rodrigo benenson <rodrigo.benenson@xxxxxxxxx>]

Thanks for the great answers !

Regards,
rodrigob.

On Wed, Nov 25, 2009 at 2:09 PM, Mark Borgerding <mark@xxxxxxxxxxxxxx> wrote:
> On 11/25/2009 06:37 AM, rodrigo benenson wrote:
>>
>> The hamming distance consists on doing XOR between two vectors and
>> then counting the number of bits in the resulting vector.
>>
>> Any suggestion on how to do this ?
>>
>
> The easy way:
> In SSE4.2, there is a POPCNT (population count) instruction that counts the
> set bits.
>
>
> The hard way:
> On processors that lack a popcnt instruction, you can add the bits in
> parallel.
> Conceptually:
> * use bitwise AND to mask a word into two words: one with even bits [ ... b4
> 0 b2 0 b0 ] and one with odd [ ... b3 0 b1 0 ]
> * shift one of the words right one bit so their LSBs line up
> * add the one-bit numbers in parallel with integer addition
> * mask the 2-bit words,right shift by 2,and add the 2-bit numbers in
> parallel (creating half as many 3 bit numbers)
> * mask the 3 bit words,right shift by 4 and add the 3-bit numbers in
> parallel
> * mask the 4-bit words,right shift by 8 and add the 4-bit numbers in
> parallel.  Each of these 4 bit numbers represents the number of set bits in
> each byte.
> * continue as many more rounds as your word length requires
>
>
> This could be extended to 128 bit words or beyond.
>
> There is an implementation for 32 bit words at
> http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetParallel
>
>
>
>