For more such problems and solns
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 <dave_and_da...@juno.com> 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 <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<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 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.
