From: ts <decoux@...>
Date: 2006-09-07T21:13:20+09:00
Subject: Re: [rubyquiz] don't understand an algorithm

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