# Don't understand an algorithm

**URL:** <https://www.ruby-forum.com/t/dont-understand-an-algorithm/67851>\
**Category:** Ruby\
**Created:** [September 7, 2006, 11:20am UTC](https://www.ruby-forum.com/t/dont-understand-an-algorithm/67851 "2006-09-07T11:20:20Z")\
**Posts on this page:** 3\
**Page:** 1

<div class="post-metadata">

**Author:** ![femto\_gary](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/f/ba8739/32.png) [@femto\_gary](https://www.ruby-forum.com/u/femto_gary)\
**Post date:** [September 7, 2006, 11:20am UTC](https://www.ruby-forum.com/t/dont-understand-an-algorithm/67851/1 "2006-09-07T11:20:20Z")

</div>

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.

---

<div class="post-metadata">

**Author:** ![femto\_gary](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/f/ba8739/32.png) [@femto\_gary](https://www.ruby-forum.com/u/femto_gary)\
**Post date:** [September 7, 2006, 2:14pm UTC](https://www.ruby-forum.com/t/dont-understand-an-algorithm/67851/2 "2006-09-07T14:14:45Z")

</div>

> > > > > “f” == femto gary [removed\_email\_address@domain.invalid](mailto:removed_email_address@domain.invalid) 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

---

<div class="post-metadata">

**Author:** ![femto\_gary](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/f/ba8739/32.png) [@femto\_gary](https://www.ruby-forum.com/u/femto_gary)\
**Post date:** [September 8, 2006, 3:30am UTC](https://www.ruby-forum.com/t/dont-understand-an-algorithm/67851/3 "2006-09-08T03:30:37Z")

</div>

Thanks , I think I got it.