Number of set bits

Hello,

I have developed two version of code to find the number of 1s in a unsigned int. It has been told to do without using loops, so later version is of recirsion methog.

Can anybodu suggest better version to this..
Thanks
RT

Code:

---

#include<stdio.h>
void main(void)
{
 unsigned int num, num_of_bits;// = 0;
 unsigned int mask = 0x1;
// printf("0x%x\n",mask);
 printf("Please enter the number:");
 scanf("%d",&num);
 /*while ( mask )
 {
  if (num & mask)
  num_of_bits++;
  mask = mask<<1;
 }*/
 /*while (num)
 {
  if ( num & mask )
  num_of_bits++;
  num = num >> 1;
 }*/
/* for (; (num>0) && (num&mask); num = num>>1)
  num_of_bits++;
 printf("Number of bits = %d\n",num_of_bits);*/
 num_of_bits = number_of_bits(num);
 printf("Number of bits = %d\n",num_of_bits);
}
unsigned int number_of_bits(unsigned int num)
{
 static unsigned int num_bits = 0;
 if ( !num )
  return num_bits;
 if ( num & 0x01 )
 {
  number_of_bits(num = (num >> 1));
  num_bits = num_bits+1;
 }
 else
 {
  number_of_bits(num = (num >> 1));
 }
 return num_bits;
}

---

Code:

---

#include <stdio.h>

int main(void)
{
    printf("%d", bit(255));
    return 0;
}

int bit(unsigned int num)
{
    int on = num % 2;
    if (!(num /= 2))
        return on;
    else   
        return on + bit(num);
}

---

"num % 2" will equal 1 if the last digit of the binary "num" is a 1, or 0 if the last digit is a 0.

i.e.
num = 101110
num % 2 = 0

num = 101111
num % 2 = 1

then you divide by 2 to get rid of that bit and onto the next one

i.e.
num = 1011011
num / 2 = 101101

num = 1101
num / 2 = 110


oh, and always use int main never void main.

Steve's 'Cute Code' collection shows a loopless trick to "Count the number of '1' bits in a 32 bit word":

Code:

---

  n = (n & 0x55555555) + ((n & 0xaaaaaaaa) >> 1);
  n = (n & 0x33333333) + ((n & 0xcccccccc) >> 2);
  n = (n & 0x0f0f0f0f) + ((n & 0xf0f0f0f0) >> 4);
  n = (n & 0x00ff00ff) + ((n & 0xff00ff00) >> 8);
  n = (n & 0x0000ffff) + ((n & 0xffff0000) >> 16);

---

[edit]This has come up here a couple times, too.

> void main(void)
125 posts and still using void main
Tsk Tsk!!!

nice link Dave. here's another :
http://graphics.stanford.edu/%7Eseander/bithacks.html

Quote:

---

> void main(void)
125 posts and still using void main
Tsk Tsk!!!

---

Will correct it next time onwards..

Difficult to break bad habits...

RT

Quote:

---

Originally Posted by Dave_Sinkula

Steve's 'Cute Code' collection shows a loopless trick to "Count the number of '1' bits in a 32 bit word":

Code:

---

  n = (n & 0x55555555) + ((n & 0xaaaaaaaa) >> 1);
  n = (n & 0x33333333) + ((n & 0xcccccccc) >> 2);
  n = (n & 0x0f0f0f0f) + ((n & 0xf0f0f0f0) >> 4);
  n = (n & 0x00ff00ff) + ((n & 0xff00ff00) >> 8);
  n = (n & 0x0000ffff) + ((n & 0xffff0000) >> 16);

---

[edit]This has come up here a couple times, too.

---

You could use a lookup table if you want it faster. :D

Quzah.

Code:

---

  n = (n & 0x55555555) + ((n & 0xaaaaaaaa) >> 1);
  n = (n & 0x33333333) + ((n & 0xcccccccc) >> 2);
  n = (n & 0x0f0f0f0f) + ((n & 0xf0f0f0f0) >> 4);
  n = (n & 0x00ff00ff) + ((n & 0xff00ff00) >> 8);
  n = (n & 0x0000ffff) + ((n & 0xffff0000) >> 16);

---

Can anybody explain, how does this work?

[off topic]
http://www.sjbaker.org/steve/software/cute_code.html
i had no idea you could do this in a switch statement

Code:

---

int a = some_number ;

 int n = ( a + 4 ) / 5 ;

 switch ( a % 5 )
 {
  case 0: do
          {
            putchar ( '*' ) ;
  case 4:  putchar ( '*' ) ;
  case 3:  putchar ( '*' ) ;
  case 2:  putchar ( '*' ) ;
  case 1:  putchar ( '*' ) ;
          } while ( --n ) ;
 }

 printf ( "\n" ) ;

---

[/off topic]