The first statement partitions i into 2-bit groups and replaces each 2 bit group with the number of 1-bits set in that group. The second statement partitions the number into 4-bit groups and adds together the two 2-bit groups in each to get the number of 1-bits originally set in that 4-bit group. The last statement partitions the number into 8-bit groups and adds the two 4-bit groups in each to get the number of 1-bits in the 8-bit group. Then the multiplication adds the 8-bit groups, leaving the sum in the upper 8 bits of the number. The shift right-justifies the sum in the word.
Dave On Jan 18, 10:54 am, Manisha <[email protected]> wrote: > This is the very efficient code for counting set bits. I am not able > to understand whats the algo/logic behind it. I tried running this > code, it gives correct output but don't know why and how? > > Could anybody explain the logic with generic example? > int NumberOfSetBits(int i) > { > i = i - ((i >> 1) & 0x55555555); > i = (i & 0x33333333) + ((i >> 2) & 0x33333333); > return ((i + (i >> 4) & 0xF0F0F0F) * 0x1010101) >> 24; > > } > > I am sorry for posting this C code here and many of you might not be > in touch with C. I would be happy to explain if any of the C related > stuff is troubling you in this question.
-- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
