The n<3 condition is the base case. For n=0,1, or 2 the answer is n. x is floor(log2(n))
This can be computed in constant time by the built in function provided. It is the same as the position of the highest bit set in n. Then the number of bits in 0..n is the number of times the xth bit is set plus the number of bits in 0..n-2^x. That is what the last line computes. Don On Friday, June 21, 2013 1:42:08 PM UTC-4, shubham saini wrote: > > thanx Don for your algos, bt i m not able to understand your second > approach can you please explain it a liitle > > > On Fri, Jun 21, 2013 at 9:50 PM, Don <[email protected] <javascript:>>wrote: > >> int bitCount(int n) >> { >> if (n < 3) return n; >> int x=31-__builtin_clz(n); >> n -= 1<<x; >> return x*(1<<(x-1)) + bitCount(n) + n + 1; >> >> } >> >> On Thursday, June 20, 2013 11:03:35 PM UTC-4, shubham saini wrote: >> >>> How to count no of set bits for all numbers from 1 to n for a given n... >>> >>> i knew brute force any better solution ?? >>> >> -- >> You received this message because you are subscribed to the Google Groups >> "Algorithm Geeks" group. >> To unsubscribe from this group and stop receiving emails from it, send an >> email to [email protected] <javascript:>. >> >> >> > > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To unsubscribe from this group and stop receiving emails from it, send an email to [email protected].
