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

  1. #16
    Fountain of knowledge.
    Join Date
    May 2006
    Posts
    794
    Quote Originally Posted by swoopy
    Well maybe Prelude will post one then. Hopefully without a lookup table though. That kind of takes the fun out of it.
    Well I hope he doesn't post the table!!!
    Not sure what he intends to do, but I think the OP's program is about as good as it gets all things considered.

  2. #17
    Fountain of knowledge.
    Join Date
    May 2006
    Posts
    794
    Quote Originally Posted by Ken Fitlike
    He cross-posted as Daved mentioned.
    I didn't see that before I posted, anyway his code didn't look much like C++ to me
    as I could understand it!!

  3. #18
    Anti-Poster
    Join Date
    Feb 2002
    Posts
    1,401
    For an entirely non-portable way:
    Code:
    long binaryCount(long number)
    {
    	number = (number & 0x55555555) + ((number & 0xaaaaaaaa) >> 1);
    	number = (number & 0x33333333) + ((number & 0xcccccccc) >> 2);
    	number = (number & 0x0f0f0f0f) + ((number & 0xf0f0f0f0) >> 4);
    	number = (number & 0x00ff00ff) + ((number & 0xff00ff00) >> 8);
    	return   (number & 0x0000ffff) + ((number & 0xffff0000) >> 16);
    }
    That assumes 4 byte longs.
    If I did your homework for you, then you might pass your class without learning how to write a program like this. Then you might graduate and get your degree without learning how to write a program like this. You might become a professional programmer without knowing how to write a program like this. Someday you might work on a project with me without knowing how to write a program like this. Then I would have to do you serious bodily harm. - Jack Klein

  4. #19
    Cat without Hat CornedBee's Avatar
    Join Date
    Apr 2003
    Posts
    8,895
    Code:
    int mask = ...;
    int count;
    asm("ctpop %1, %0" : "=r"(count) : "r"(mask));
    This will, of course, only compile with GCC on an Alpha machine, but hey, you wanted efficient, right? No one said anything about portable.
    All the buzzt!
    CornedBee

    "There is not now, nor has there ever been, nor will there ever be, any programming language in which it is the least bit difficult to write bad code."
    - Flon's Law

  5. #20
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660
    Boring I know, but what can you do?
    Code:
    #include <stdio.h>
    
    int
    main (void)
    {
      unsigned int v = 0xFF0F;
      unsigned int w = v - ((v >> 1) & 0x55555555);                    
      unsigned int x = (w & 0x33333333) + ((w >> 2) & 0x33333333);     
      unsigned int c = ((x + (x >> 4) & 0xF0F0F0F) * 0x1010101) >> 24; 
      printf ("%d\n", c);
      return 0;
    }
    Whole bunch of 'em here
    http://graphics.stanford.edu/~seander/bithacks.html
    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.

  6. #21
    Supermassive black hole cboard_member's Avatar
    Join Date
    Jul 2005
    Posts
    1,709
    Damn it Salem. I get all the way to your post thinking "I've got a great link to post".
    Good class architecture is not like a Swiss Army Knife; it should be more like a well balanced throwing knife.

    - Mike McShaffry

  7. #22
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    Quote Originally Posted by esbo
    I didn't see that before I posted, anyway his code didn't look much like C++ to me
    as I could understand it!!
    Yeah I bet that was a real feat.


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

  8. #23
    Fountain of knowledge.
    Join Date
    May 2006
    Posts
    794
    Well you could change:-
    Code:
    for ( i = 0; i < sizeof(int)*8 ; i++ )
    if ( mask<<i & var) count++ ;
    to (to get rid of the 'if')
    Code:
    for ( i = 0; i < sizeof(int)*8 ; i++ ) 
    count+= (mask& var>>i );
    or even
    Code:
    for ( i = 0; i < sizeof(int)*8 ; i++, count+= (mask& var>>i ));

  9. #24
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    Nevermind. I'm slow today. All of these have already been covered probably, but if not, there ya go.



    Quzah.
    Last edited by quzah; 09-12-2006 at 04:43 PM.
    Hope is the first step on the road to disappointment.

  10. #25
    Registered User
    Join Date
    Sep 2006
    Posts
    10
    The fastest way I found is using lookup table. For integer, 4 bytes long, it takes 4 additional operators only.

    And, this :
    Code:
    for ( i = 0; i < sizeof(int)*8 ; i++ ) 
    count+= (mask& var>>i );
    Also, great idea~!

    Thanks a lot, folks.

    ====================

    About the cross-posted, I posted this topic in C++ board first. It's wrong place for my target language, C. Then, I posted it in C board again. Sorry. Thank you, Ken Fitlike, for adding code tags.

  11. #26
    Registered User
    Join Date
    Oct 2001
    Posts
    2,934
    You could even do this:
    Code:
    int count_ones(unsigned int var)
    {
       unsigned int mask = 0x1;
       int count = 0;
       while (var != 0)
       {
          count += var & mask;
          var >>= 1;
       }
       return count;
    }
    I prefer the if so I'd do:
    Code:
    int count_ones(unsigned int var)
    {
       unsigned int mask = 0x1;
       int count = 0;
       while (var != 0)
       {
          if (var & mask)
             count++;
          var >>= 1;
       }
       return count;
    }

  12. #27
    Fountain of knowledge.
    Join Date
    May 2006
    Posts
    794
    I guess the fastest way would be really huge look up table, for a 32 bit int you would need
    4 gigabites+ of memory though.
    For a 64 bit int well, you might need a loan to buy the memory

    The program might take a while to load but once loaded it would run like lightening!!
    Last edited by esbo; 09-12-2006 at 05:13 PM.

  13. #28
    Gawking at stupidity
    Join Date
    Jul 2004
    Location
    Oregon, USA
    Posts
    3,218
    Quote Originally Posted by esbo
    I guess the fastest way would be really huge look up table, for a 32 bit int you would need
    4 gigabites+ of memory though.
    For a 64 bit int well, you might need a loan to buy the memory

    The program might take a while to load but one loaded it would run like lightening!!
    Of course, you could just use, say, a 4-bit lookup table and do 8 lookups.
    If you understand what you're doing, you're not learning anything.

  14. #29
    Fountain of knowledge.
    Join Date
    May 2006
    Posts
    794
    Quote Originally Posted by itsme86
    Of course, you could just use, say, a 4-bit lookup table and do 8 lookups.
    You could but it would take 8 times longer to complete (at least).

  15. #30
    Lurking whiteflags's Avatar
    Join Date
    Apr 2006
    Location
    United States
    Posts
    9,613
    > You could but it would take 8 times longer to complete (at least).
    Performance isn't always a problem, and this is beyond the scope of the original question.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. memory issue
    By t014y in forum C Programming
    Replies: 2
    Last Post: 02-21-2009, 12:37 AM
  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, 10:43 AM
  5. Im so lost at . .
    By hermit in forum C Programming
    Replies: 18
    Last Post: 05-15-2002, 01:26 AM