Did you actually try the code by hand on a number to see what it does? If you do, you will see that the first statement replaces the bits in each pair of bit positions with the number of bits in those positions. The second adds the bits in each pair of pairs, replacing each nibble with the number of bits originally set in that nibble. Etc.
Dave On Jun 22, 10:54 am, divya jain <[email protected]> wrote: > @ dave > how did u come to this formula... m nt getting the logic.. > > @ sathaiah > yes u r rite > > On 22 June 2010 19:32, chitta koushik <[email protected]> wrote: > > > > > For more such problems and solns > > >http://graphics.stanford.edu/~seander/bithacks.html<http://graphics.stanford.edu/%7Eseander/bithacks.html> > > > for (c = 0; v; c++) > > { > > v &= v - 1; // clear the least significant bit set > > } > > > O(k) -- no. of bits set in the number > > > --Koushik C > > > On Tue, Jun 22, 2010 at 7:16 PM, Dave <[email protected]> wrote: > > >> Assuming 32 bit integers: > >> n = ((x >> 1) & 0x55555555) + (x & 0x55555555) > >> n = ((n >> 2) & 0x33333333) + (n % 0x33333333) > >> n = ((n >> 4) & 0x0F0F0F0F) + (n & 0x0F0F0F0F) > >> n = ((n >> 8) & 0x00FF00FF) + (n & 0x00FF00FF) > >> n = ((n >>16) & 0x0000FFFF) + (n & 0x0000FFFF) > > >> n now is the number of bits set in x. Time is O(1). > > >> Dave > > >> On Jun 22, 6:26 am, divya <[email protected]> wrote: > >> > find the no. of bits set in a no. in logn time > > >> -- > >> 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]<algogeeks%2bunsubscr...@googlegroups.com> > >> . > >> For more options, visit this group at > >>http://groups.google.com/group/algogeeks?hl=en. > > > -- > > 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]<algogeeks%2bunsubscr...@googlegroups.com> > > . > > For more options, visit this group at > >http://groups.google.com/group/algogeeks?hl=en.- Hide quoted text - > > - Show quoted text - -- 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.
