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 <sweetdivya....@gmail.com> 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 algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
