This code takes O(logn) steps. The first solution proposed takes
O(number of 1s)steps(which is less than O(logn) average case), the
other approach is to some of the bit hacks in the link, there are
methods to do that in O(loglogn) if n is fit within the word length of
the processor though they are
how abt my code
#include
int count1bitsn(int n)
{
int count=0;
while(n)
{
count+=n&1;
n=n>>1;
}
return count;
}
int main()
{
int n;
printf("Enter the value of n\n");
scanf("%d",&n);
how abt my code
#include
int count1bitsn(int n)
{
int count=0;
while(n)
{
count+=n&1;
n=n>>1;
}
}
int main()
{
int n;
printf("Enter the value of n\n");
scanf("%d",&n);
printf("Answer
The standard link
http://graphics.stanford.edu/~seander/bithacks.html
--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com
To unsubs
I have a simple method.
Let hash[x]=count of 1 bits in x for 0<=x<2^16
So for any 32-bit integer x, the count of 1 bits is hash[x&0x]
+hash[x>>16].
We can pre-calculate all hash[] value.
On Mar 21, 1:24 pm, "hijkl" <[EMAIL PROTECTED]> wrote:
> How to count the 1 bits in a integer?
> int C
Hi,,
Think the No of 1 bits can be found in o(k) where k is the no of bits
set
while((n & (n-1)) >= 0)
{
c++;
n = n & (n-1);
printf(">> n %d Cnt %d \n",n,c);
if(!n)
break;
}
printf("Cnt %d \n",c);
--~--~-~--~~~---~--~
