[algogeeks] Re: count the 1 bits in integer

[Karthik Singaram L]

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 ugly.

--~--~-~--~~~---~--~~
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 unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~--~~~~--~~--~--~---

[algogeeks] Re: count the 1 bits in integer

[vim]

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);
  printf("Answer=%d\n",count1bitsofn(n));

}

On Mar 22, 12:39 am, "Karthik Singaram L" <[EMAIL PROTECTED]>
wrote:
> The standard linkhttp://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 unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~--~~~~--~~--~--~---

[algogeeks] Re: count the 1 bits in integer

[vim]

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=%d\n",count1bitsofn(n));
}






On Mar 22, 12:39 am, "Karthik Singaram L" <[EMAIL PROTECTED]>
wrote:
> The standard linkhttp://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 unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~--~~~~--~~--~--~---

[algogeeks] Re: count the 1 bits in integer

[Karthik Singaram L]

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 unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~--~~~~--~~--~--~---

[algogeeks] Re: count the 1 bits in integer

[stone]

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 Count1Bits(int i);
> How about this function is used very often?


--~--~-~--~~~---~--~~
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 unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~--~~~~--~~--~--~---

[algogeeks] Re: count the 1 bits in integer

[Balachander]

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);


--~--~-~--~~~---~--~~
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 unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~--~~~~--~~--~--~---