This is called Popcount Problem. I really want to know how gcc __builtin_popcount does.
On 1月19日, 上午2时20分, Dave <[email protected]> wrote: > 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.
