Anand, I don't see how to correlate what you have written with my algorithm. Here is a numerical example for the number 0xA7, = 1010 0111 in binary.
First step: 1010 0111 & 0101 0101 = 0000 0101 1010 0111 >> 1 = 0101 0011 0101 0011 & 01010101 = 0101 0001 0000 0101 + 0101 0001 = 0101 0110 Second step: 0101 0110 & 0011 0011 = 0001 0010 0101 0110 >> 2 = 0001 0101 0001 0101 & 0011 0011 = 0001 0001 0001 0010 + 0001 0001 = 0010 0011 Third step: 0010 0011 & 0000 1111 = 0000 0011 0010 0011 >> 4 = 0000 0010 0000 0010 & 0000 1111 = 0000 0010 0000 0011 + 0000 0010 = 0000 0101 The remaining steps don't change this 8 bits since there are no higher order bits to contribute to the count of one-bits, so the answer is 0000 0101 = 5, which is the number of one-bits in 15. Dave On Jun 23, 4:33 pm, Anand <[email protected]> wrote: > if we do it in binary. Here is how it goes > > Number : 15 > Step 1 1010 : 0111 & 0101 + 1111 & 0101. > Step2: 0100: 0010 & 0011 + 1010 & 0011 > Step3: 0100: 0000 & 0F0F + 0100 & 0F0F; > Step4: 0100: 0000 & FFFF +0100 &FFFF; > > Final Answer: 4.Stiil cud not get the logic > > > > On Wed, Jun 23, 2010 at 12:18 PM, Dave <[email protected]> wrote: > > Anand, do it in binary. > > > Dave > > > On Jun 23, 1:29 pm, Anand <[email protected]> wrote: > > > @Dave I tried your logic on 15 it got converted to 10, 4, 4,4. But still > > > could not understand the logic could you please explain? > > > > On Tue, Jun 22, 2010 at 9:34 PM, Dave <[email protected]> wrote: > > > > 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<http://graphics.stanford.edu/~seander/bithacks.html> > > > > > <http://graphics.stanford.edu/%7Eseander/bithacks.html<http://graphics.stanford.edu/~seander/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> > > <algogeeks%2bunsubscr...@googlegroups.com> > > > > <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> > > <algogeeks%2bunsubscr...@googlegroups.com> > > > > <algogeeks%2bunsubscr...@googlegroups.com> > > > > > > . > > > > > > For more options, visit this group at > > > > > >http://groups.google.com/group/algogeeks?hl=en.-Hidequoted 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]<algogeeks%2bunsubscr...@googlegroups.com> > > <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]<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.
