# Thread: Number of set bits

1. ## 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;
scanf("%d",&num);
{
num_of_bits++;
}*/
/*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;
}```

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

3. 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);```
This has come up here a couple times, too.

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

5. > void main(void)
125 posts and still using void main
Tsk Tsk!!!
Will correct it next time onwards..

RT

6. 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);```
This has come up here a couple times, too.
You could use a lookup table if you want it faster.

Quzah.

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

8. [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]