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 <[email protected]> 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 <[email protected]> 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 [email protected].
>
>
>
--
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 [email protected].
