[lnkForumImage]
TotalShareware - Download Free Software
Confronta i prezzi di migliaia di prodotti.
Asp Forum
 Home | Login | Register | Search 


 

Forums >

comp.lang.ruby

[rubyquiz] don't understand an algorithm

femto

9/7/2006 9:20:00 AM

hello all,
I'm running the SCRABBLE STEMS in ruby quiz book.
the second algorithm has the following code snipet:

hash.each do |k, v|
v = (v & 0x5555555) + ((v>>1) & 0x5555555)
v = (v & 0x3333333) + ((v>>2) & 0x3333333)
v = (v & 0xf0f0f0f) + ((v>>4) & 0xf0f0f0f)
v = (v & 0x0ff00ff) + ((v>>8) & 0x0ff00ff)
v = (v & 0x000ffff) + ((v>>16) & 0x000ffff)
count[k] = v if v >= cutoff
end

I don't get why the many lines v= ....
is equivlent to sprint("%b", v).count("1"),
ie. count the occurrence of 1 in binary v.
2 Answers

ts

9/7/2006 12:13:00 PM

0

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

femto

9/8/2006 1:27:00 AM

0

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