From: femto gary <femtowin@...>
Date: 2006-09-08T10:27:19+09:00
Subject: Re: [rubyquiz] don't understand an algorithm

Thanks , I think I got it.

On 9/7/06, ts <decoux@moulon.inra.fr> wrote:
> >>>>> "f" == femto gary <femtowin@gmail.com> writes:
>
>
>  it's a parallel count
>
> f> v = (v & 0x5555555) + ((v>>1) & 0x5555555)
>
>  Imagine that v is splitted in pair of bits, after this line each pair contains
>  the number of ones in the two bit positions in the original v
>
> moulon% ruby -e 'p "%b" % 0x5555555'
> "101010101010101010101010101"
> moulon%
>
> f> v = (v & 0x3333333) + ((v>>2) & 0x3333333)
>
>  Each nibble contains the number of ones in the 4 bit positions
>
> moulon% ruby -e 'p "%b" % 0x3333333'
> "11001100110011001100110011"
> moulon%
>
> f> v = (v & 0xf0f0f0f) + ((v>>4) & 0xf0f0f0f)
>
>  You have the number of ones in the 8 bits positions
>
> moulon% ruby -e 'p "%b" % 0xf0f0f0f'
> "1111000011110000111100001111"
> moulon%
>
> f> v = (v & 0x0ff00ff) + ((v>>8) & 0x0ff00ff)
> f> v = (v & 0x000ffff) + ((v>>16) & 0x000ffff)
>
>  and finally the total number of ones in v.
>
>
> Guy Decoux
>
>
>
>
>
>
>


-- 
Best Regards
femto http://femto.blogdriver.com