int bitCount[N];
bitCount[0] = 0;
for(int i = 1; i N; ++i)
bitCount[i] = bitCount[i1] + (i1);
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
int bitCount(int n)
{
if (n 3) return n;
int x=31-__builtin_clz(n);
n -= 1x;
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
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 dondod...@gmail.com wrote:
int bitCount(int n)
{
if (n 3) return n;
int x=31-__builtin_clz(n);
n -= 1x;
return x*(1(x-1)) +
The n3 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
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);
