here is the code ... my solution covers the range for all integers ..
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
int BT[256];
int main(){
int t=0;
BT[0]=0;
for (int i = 0; i < 256; i++){
BT[i] = (i & 1) + BT[i / 2];
}
int s=1;
int e=0;
//scanf("%d",&s); //not reading s here just keeping it 1
scanf("%d",&e);
//printf("%d %d",s,e);
int range=e-s;
int i=0;
int ct=0;
for(i=0;i<=range;i++){
unsigned int v=s+i;
ct+=BT[v & 0xff] + BT[(v >> 8) & 0xff] + BT[(v >> 16) & 0xff] + BT[v
>> 24];
printf("%d\n",ct);
}
return 0;
}
On Fri, Jun 21, 2013 at 11:44 PM, Don <dondod...@gmail.com> wrote:
> 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 <dond...@gmail.com> 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 algogeeks+...@**googlegroups.com.
>>>
>>>
>>>
>>
>> --
> 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 algogeeks+unsubscr...@googlegroups.com.
>
>
>
--
Regards,
Sourabh Kumar Jain
+91-8971547841
--
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 algogeeks+unsubscr...@googlegroups.com.
