[rubyquiz] don't understand an algorithm

ruby-talk
1

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

it's a parallel count

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%

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%

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%

v = (v & 0x0ff00ff) + ((v>>8) & 0x0ff00ff)
v = (v & 0x000ffff) + ((v>>16) & 0x000ffff)

and finally the total number of ones in v.

Guy Decoux

3

Thanks , I think I got it.

ยทยทยท

On 9/7/06, ts <decoux@moulon.inra.fr> wrote:

it's a parallel count

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

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

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

> v = (v & 0x0ff00ff) + ((v>>8) & 0x0ff00ff)
> v = (v & 0x000ffff) + ((v>>16) & 0x000ffff)

and finally the total number of ones in v.

Guy Decoux

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