Re: [eigen] Vectorized Hamming distance |

[ Thread Index | Date Index | More lists.tuxfamily.org/eigen Archives ]

*To*: eigen@xxxxxxxxxxxxxxxxxxx*Subject*: Re: [eigen] Vectorized Hamming distance*From*: rodrigo benenson <rodrigo.benenson@xxxxxxxxx>*Date*: Wed, 25 Nov 2009 17:44:59 +0100*Dkim-signature*: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=gamma; h=domainkey-signature:mime-version:received:in-reply-to:references :from:date:message-id:subject:to:content-type :content-transfer-encoding; bh=XbYy45X3VA506QdVPOrppQLm+U6FXMZ5E9u3+1aK+Zc=; b=JbIh7rjwyw4ZMKIewDMT/HSN1cHMoMmDIfVfeM9ra1CXmSAHuKbjYq2spjpEqScGpS h1U3kooSbb0FMk1RlCvX06nUTRSRujYqRfUuAxbx7G9lxOrXY3LxO63UMkN+lhz29VUr ZCt+1Trkqojq/WozraWju0ZcZ/sNlm5k43ybw=*Domainkey-signature*: a=rsa-sha1; c=nofws; d=gmail.com; s=gamma; h=mime-version:in-reply-to:references:from:date:message-id:subject:to :content-type:content-transfer-encoding; b=qMOVBv4QDWz2a9KVuolwN9memjBbJF4+mr1VHnI1smTlacml2GFGPnn+zT3AZEfcoq NRFwGAuH2Zb8YAefooujRB3kaXt9CmWrV31+fcYJ31iXPRhKZgs0slY+ZyspT6hPZ0Id NinS6gOAhfRFZc4HttqRcnKlrrVtiumAK7XN8=

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 > > > >

**References**:**[eigen] Vectorized Hamming distance***From:*rodrigo benenson

**Re: [eigen] Vectorized Hamming distance***From:*Mark Borgerding

**Messages sorted by:**[ date | thread ]- Prev by Date:
**Re: [eigen] Status of unsupported modules** - Next by Date:
**Re: [eigen] New(?) way to make using SIMD easier** - Previous by thread:
**Re: [eigen] Vectorized Hamming distance** - Next by thread:
**[eigen] Eigen 2.0.10 released**

Mail converted by MHonArc 2.6.19+ | http://listengine.tuxfamily.org/ |