How many bits are '1' in an integer variable?

This is a discussion on How many bits are '1' in an integer variable? within the C Programming forums, part of the General Programming Boards category; Hi folks, I am trying to find a more efficient way to count "How many bits are '1' in an ...

  1. #1
    Registered User
    Join Date
    Sep 2006
    Posts
    10

    How many bits are '1' in an integer variable?

    Hi folks,

    I am trying to find a more efficient way to count "How many bits are
    '1' in an integer variable?".

    I still have no idea to count the bits except using a loop and "if"
    statements.
    Could you know any other more efficient way?

    Cuthbert

    Code:
    int main (void)
    {
    int var = 0xFF0F;
    int i, count = 0;
    int mask = 1;
    for ( i = 0; i < sizeof(int)*8 ; i++ )
    if ( mask<<i & var) count++ ;
    
    printf("%d\n", count);
    
    return 0;
    }
    Last edited by Ken Fitlike; 09-12-2006 at 01:11 PM. Reason: code tags added

  2. #2
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,796
    >I am trying to find a more efficient way to...
    Why do you need a more efficient way?

    >Could you know any other more efficient way?
    Yes, of course. Use a lookup table.
    My best code is written with the delete key.

  3. #3
    {Jaxom,Imriel,Liam}'s Dad Kennedy's Avatar
    Join Date
    Aug 2006
    Location
    Alabama
    Posts
    1,065
    One change you could make to speed this up (just a very little bit) would be to change:
    Code:
    if (mask <<i & var) count++;
    to
    Code:
    {if (mask & var) count++;
    mask <<= 1;}
    to get rid of the * in the code, which is longer than doing a bitwise shift.

  4. #4
    Registered User
    Join Date
    Oct 2001
    Posts
    2,934
    >Could you know any other more efficient way?
    Code:
    int var = 0xFF0F;
    printf("%d\n", (int) std::bitset<sizeof(int)*8>(var).count());

  5. #5
    (?<!re)tired Mario F.'s Avatar
    Join Date
    May 2006
    Location
    Portugal
    Posts
    7,412
    A non-portable way is to use itoa() if your compiler supports it, with a radix of 2. This will return a C-style string you can then count for 1s.

    A portable way involves the use of recursion as seen here http://www.engin.umd.umich.edu/CIS/c...pp/binary.html, changing it where appropriate to count 1s.

    Both options are faster than what you are doing.

    EDIT: Well... swoopy's faster no doubt
    The programmer’s wife tells him: “Run to the store and pick up a loaf of bread. If they have eggs, get a dozen.”
    The programmer comes home with 12 loaves of bread.


    Originally Posted by brewbuck:
    Reimplementing a large system in another language to get a 25% performance boost is nonsense. It would be cheaper to just get a computer which is 25% faster.

  6. #6
    Registered User
    Join Date
    Jan 2005
    Posts
    7,317
    >> sizeof(int)*8
    Maybe sizeof(int)*CHAR_BIT instead.

  7. #7
    Fountain of knowledge.
    Join Date
    May 2006
    Posts
    794
    Quote Originally Posted by swoopy
    >Could you know any other more efficient way?
    Code:
    int var = 0xFF0F;
    printf("%d\n", (int) std::bitset<sizeof(int)*8>(var).count());
    What won't compile for me!! (c++?)

  8. #8
    Hardware Engineer
    Join Date
    Sep 2001
    Posts
    1,398

    Thumbs up I'm glad to see you're using hex!

    I'm glad to see you're using hex! I always recommend hex when working with binary numbers & bitwise operations. Even if the 'assignment' doesn't required it, displaying the variable in hex makes it much easier to "see" what your program is doing.

    Once you understand the relationship between hex and binary, you can look at 0xFF0F and instantly see that there are 12 "ones".

  9. #9
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,796
    >What won't compile for me!!
    Maybe it's because you're using K&R C.
    My best code is written with the delete key.

  10. #10
    Fountain of knowledge.
    Join Date
    May 2006
    Posts
    794
    Quote Originally Posted by Prelude
    >What won't compile for me!!
    Maybe it's because you're using K&R C.
    I am using gcc.

  11. #11
    Registered User
    Join Date
    Jan 2005
    Posts
    7,317
    The question was cross-posted to the C++ board, so presumably C++ answers are valid.

  12. #12
    Registered User
    Join Date
    Oct 2001
    Posts
    2,934
    Quote Originally Posted by Daved
    >> sizeof(int)*8
    Maybe sizeof(int)*CHAR_BIT instead.
    Yes thanks, that's would be better.

  13. #13
    Registered User
    Join Date
    Oct 2001
    Posts
    2,934
    Quote Originally Posted by esbo
    What won't compile for me!! (c++?)
    Make sure you compile as C++ (.cpp file) and #include <bitset>

  14. #14
    Fountain of knowledge.
    Join Date
    May 2006
    Posts
    794
    Quote Originally Posted by swoopy
    Make sure you compile as C++ (.cpp file) and #include <bitset>
    Well as he posted in the C forum I presume he wanted to use C?

  15. #15
    Registered User
    Join Date
    Oct 2001
    Posts
    2,934
    Quote Originally Posted by esbo
    Well as he posted in the C forum I presume he wanted to use C?
    Well maybe Prelude will post one then. Hopefully without a lookup table though. That kind of takes the fun out of it.

Page 1 of 4 1234 LastLast
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. memory issue
    By t014y in forum C Programming
    Replies: 2
    Last Post: 02-20-2009, 11:37 PM
  2. Need some help...
    By darkconvoy in forum C Programming
    Replies: 32
    Last Post: 04-29-2008, 03:33 PM
  3. Replies: 7
    Last Post: 08-19-2007, 08:10 AM
  4. load gif into program
    By willc0de4food in forum Windows Programming
    Replies: 14
    Last Post: 01-11-2006, 09:43 AM
  5. Im so lost at . .
    By hermit in forum C Programming
    Replies: 18
    Last Post: 05-15-2002, 01:26 AM

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