Thread: Counting set bits in a character.

  1. #1
    Registered User
    Join Date
    Sep 2011
    Location
    Athens , Greece
    Posts
    357

    Counting set bits in a character.

    Hello

    I have this code :

    Code:
     
    
    #include <stdio.h>
    
    int countSetBits(unsigned char ch)
    {
            unsigned int c;
    
            for( c = 0; ch; ch >>=1)
                c += ch & 1;
    
            return c;
    }
    
    int main(void)
    {
    
        unsigned char ch;
    
        printf("Enter a character: ");
        scanf(" %c" , &ch);
    
        printf(" The number of set bits (1) in character %c is : %d \n" , ch , countSetBits(ch) );
    
        return 0;
    }
    Is there any way to write the function without using a loop?

  2. #2
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    27,272
    Yes. For example, you could use a lookup table.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  3. #3
    Registered User
    Join Date
    Sep 2011
    Location
    Athens , Greece
    Posts
    357
    lookup table? I have never use this before ...

  4. #4
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    27,272
    Well, in its simplest form, given an 8-bit byte, you could have an array of 256 integers. The index of each element corresponds to a possible value of the character, and the value corresponds to the number of set bits. So, to get the count of set bits of the character, you simply access the array by index, i.e., by the value of the character.

    There are ways to compact this, and then there are yet other ways that may be harder to understand but require less space and may be as efficient.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  5. #5
    Registered User
    Join Date
    Jun 2005
    Posts
    6,815
    An alternate way is to unroll the loop.
    Right 98% of the time, and don't care about the other 3%.

    If I seem grumpy or unhelpful in reply to you, or tell you you need to demonstrate more effort before you can expect help, it is likely you deserve it. Suck it up, Buttercup, and read this, this, and this before posting again.

  6. #6
    Registered User
    Join Date
    Sep 2011
    Location
    Athens , Greece
    Posts
    357
    Quote Originally Posted by grumpy View Post
    An alternate way is to unroll the loop.
    Unroll the loop? what do you mean by that? :/

    well I am good when I have a code to read and understand but I am not so good when I have to write a code from the beginning :/

  7. #7
    Lurking whiteflags's Avatar
    Join Date
    Apr 2006
    Location
    United States
    Posts
    9,612
    He means you only need 8 lines of this:
    Code:
    c += ch & 1;
    You will have to shift ch to check the proper bit in each line, but you can do that.

  8. #8
    Registered User
    Join Date
    Sep 2011
    Location
    Athens , Greece
    Posts
    357
    But is this efficient? I think it is ungly and not readable.

    Code:
    
    int countSetBits(unsigned char ch)
    {
            unsigned int c=0;
    
            //for( c = 0; ch; ch >>=1)
                c += ch & 1;  ch >>=1;
                c += ch & 1;  ch >>=1;
                c += ch & 1;  ch >>=1;
                c += ch & 1;  ch >>=1;
                c += ch & 1;  ch >>=1;
                c += ch & 1;  ch >>=1;
                c += ch & 1;  ch >>=1;
                c += ch & 1;  ch >>=1;
    
            return c;
    }
    Last edited by Mr.Lnx; 07-13-2014 at 08:06 AM.

  9. #9
    Registered User
    Join Date
    Jun 2005
    Posts
    6,815
    Quote Originally Posted by Mr.Lnx View Post
    But is this efficient? I think it is ungly and not readable.
    In principle, it's the same efficiency or marginally better, since there doesn't have to be a branch (check a condition and jump to some place in code). It would involve more instructions written to an executable file (i.e. a bigger executable).

    Yes, doing it with a loop is often the less ugly and more readable solution. But you asked if it was possible to do it without the loop - hence effectively asked for the more ugly and less readable options. You can't have your cake and eat it too.
    Last edited by grumpy; 07-13-2014 at 08:11 AM.
    Right 98% of the time, and don't care about the other 3%.

    If I seem grumpy or unhelpful in reply to you, or tell you you need to demonstrate more effort before you can expect help, it is likely you deserve it. Suck it up, Buttercup, and read this, this, and this before posting again.

  10. #10
    Lurking whiteflags's Avatar
    Join Date
    Apr 2006
    Location
    United States
    Posts
    9,612
    It is not any less efficient. The simplest thing I can think of requires a loop as well, so you will probably be stuck with a lookup table if you must do it differently.

  11. #11
    Registered User
    Join Date
    Sep 2011
    Location
    Athens , Greece
    Posts
    357
    Yes you are right. I used the term efficient in terms of readability and beauty of code. It has nothing to do with the classic term because of condition and jumping as you said. Maybe it is completely wrong the fact that I used this term. Anyway thank you

  12. #12
    Hurry Slowly vart's Avatar
    Join Date
    Oct 2006
    Location
    Rishon LeZion, Israel
    Posts
    6,793
    as a simple mind trick
    Code:
    unsigned char count_bits(unsigned char val)
    {
      val = ((val &0xAA) >> 1 ) + (val & 0x55);
      val = ((val &0xCC) >> 2 ) + (val & 0x33);
      val = ((val &0xF0) >> 4 ) + (val & 0x0f);
      return val;
    }
    deliberatly leave the explanation out
    All problems in computer science can be solved by another level of indirection,
    except for the problem of too many layers of indirection.
    David J. Wheeler

  13. #13
    Registered User
    Join Date
    Mar 2011
    Posts
    596
    Shouldn't

    Code:
    val = ((val &0xF0) >> 4 ) + (val & 0x0f);
    be

    Code:
    val = ((val &0x07) >> 4 ) + (val & 0x07);
    ?

    Ok, I see that bits 3 and 7 would have already been forced to zero at that point.
    0x70 and 0x07 makes ihe operation a little bit clearer.

    -
    Last edited by megafiddle; 07-14-2014 at 06:42 AM.

  14. #14
    Registered User
    Join Date
    Jul 2014
    Location
    Claremore, OK, USA
    Posts
    1
    Hello, I am a new user. This is my first post.

    A 'cooler' solution would be use a lookup table, as suggested by laserlight, consisting of an array of 256 integers containing the count of ones in each possible byte 0 to 255. Then you just index into the array, with the byte in question, to get the count. Very fast. To start:

    Code:
    unsigned char count[256] = {0,1,1,2,1,2,2,3,1,2...6,7};
    Ron

  15. #15
    Registered User
    Join Date
    Mar 2009
    Posts
    344
    Quote Originally Posted by BasicPoke View Post
    Hello, I am a new user. This is my first post.

    A 'cooler' solution would be use a lookup table, as suggested by laserlight, consisting of an array of 256 integers containing the count of ones in each possible byte 0 to 255. Then you just index into the array, with the byte in question, to get the count. Very fast.
    Don't confuse fewer lines of C code with fast. Worst case (the array isn't in cache) this will be much slower than a loop or some of the other tricks mentioned above.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 1
    Last Post: 02-21-2012, 07:42 PM
  2. Viewing and Counting Set Bits in an Integer
    By Adak in forum C Programming
    Replies: 9
    Last Post: 08-13-2010, 07:05 PM
  3. Replies: 7
    Last Post: 08-19-2007, 08:10 AM
  4. Help counting number of bits set in an integer
    By JayDiddums10 in forum C Programming
    Replies: 5
    Last Post: 12-07-2006, 03:21 PM
  5. Character counting
    By Jas11 in forum C++ Programming
    Replies: 3
    Last Post: 04-21-2005, 02:55 AM