Number of set bits

**Roaring_Tiger** · 09-20-2004

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

**Brian** · 09-20-2004

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.

**Dave_Sinkula** · 09-20-2004

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.

**Salem** · 09-20-2004

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

**viaxd** · 09-20-2004

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

**Roaring_Tiger** · 09-20-2004

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

Will correct it next time onwards..

Difficult to break bad habits...

RT

**quzah** · 09-20-2004

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.

Quzah.

**Roaring_Tiger** · 09-22-2004

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?

**sand_man** · 09-22-2004

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

Thread: Number of set bits

Thread Tools

Search Thread

Display

Number of set bits

Similar Threads

Help counting number of bits set in an integer

Logical errors with seach function

The new FAQ

C help for network animator

problem with open gl engine.