Number of set bits

This is a discussion on Number of set bits within the C Programming forums, part of the General Programming Boards category; Hello, I have developed two version of code to find the number of 1s in a unsigned int. It has ...

  1. #1
    Registered User
    Join Date
    Feb 2003
    Posts
    175

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

  2. #2
    Registered User
    Join Date
    Jan 2002
    Location
    Vancouver
    Posts
    2,220
    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.
    Last edited by Brian; 09-20-2004 at 12:41 PM.

  3. #3
    Just Lurking Dave_Sinkula's Avatar
    Join Date
    Oct 2002
    Posts
    5,006
    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.
    Last edited by Dave_Sinkula; 09-20-2004 at 12:44 PM.
    7. It is easier to write an incorrect program than understand a correct one.
    40. There are two ways to write error-free programs; only the third one works.*

  4. #4
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,484
    > void main(void)
    125 posts and still using void main
    Tsk Tsk!!!
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

  5. #5
    ~viaxd() viaxd's Avatar
    Join Date
    Aug 2003
    Posts
    246
    :wq

  6. #6
    Registered User
    Join Date
    Feb 2003
    Posts
    175
    > void main(void)
    125 posts and still using void main
    Tsk Tsk!!!
    Will correct it next time onwards..

    Difficult to break bad habits...

    RT

  7. #7
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    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.

    Quzah.
    Hope is the first step on the road to disappointment.

  8. #8
    Registered User
    Join Date
    Feb 2003
    Posts
    175
    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?

  9. #9
    ---
    Join Date
    May 2004
    Posts
    1,379
    [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]

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Help counting number of bits set in an integer
    By JayDiddums10 in forum C Programming
    Replies: 5
    Last Post: 12-07-2006, 02:21 PM
  2. Logical errors with seach function
    By Taka in forum C Programming
    Replies: 4
    Last Post: 09-18-2006, 05:20 AM
  3. The new FAQ
    By Hammer in forum A Brief History of Cprogramming.com
    Replies: 34
    Last Post: 08-30-2006, 10:05 AM
  4. C help for network animator
    By fastshadow in forum Tech Board
    Replies: 7
    Last Post: 03-17-2006, 02:44 AM
  5. problem with open gl engine.
    By gell10 in forum Game Programming
    Replies: 1
    Last Post: 08-21-2003, 04:10 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21