Count Bits

This is a discussion on Count Bits within the C Programming forums, part of the General Programming Boards category; How to count number of 1's in a 32 bit integer (do not loop throught the bits). thanx krithi...

  1. #1
    Registered User
    Join Date
    Oct 2002
    Posts
    12

    Unhappy Count Bits

    How to count number of 1's in a 32 bit integer (do not loop throught the bits).

    thanx
    krithi

  2. #2
    moi
    moi is offline
    Registered User moi's Avatar
    Join Date
    Jul 2002
    Posts
    946

    Re: Count Bits

    Originally posted by krithi
    (do not loop throught the bits).
    well then how do you intend to do it? every method i can think of is, in one way or another, looping through the bits.
    hello, internet!

  3. #3
    Skunkmeister Stoned_Coder's Avatar
    Join Date
    Aug 2001
    Posts
    2,572
    hmmm heres a loop through the bits method...
    Code:
    #include <stdio.h>
    
    int main()
    {
        int value=0x1234;// any number will do
        int count=0; // set bits
        int i;
        for(i=0;i<32;i++)
           if ((value<<i)&1) ++count;
        printf("Number of set bits is %d\n",count);
        return 0;
    }
    without looping through the bits im not so sure. Lookup tables will work but thats a hell of a lot more work.
    Free the weed!! Class B to class C is not good enough!!
    And the FAQ is here :- http://faq.cprogramming.com/cgi-bin/smartfaq.cgi

  4. #4
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,796
    >How to count number of 1's in a 32 bit integer (do not loop throught the bits).
    Perhaps you're looking for this well known bit fiddling snippet?
    Code:
    unsigned countbits32_no_loop ( unsigned x )
    {
       x = ( 0x55555555 & x ) + ( 0x55555555 & ( x >> 1 ) );
       x = ( 0x33333333 & x ) + ( 0x33333333 & ( x >> 2 ) );
       x = ( 0x0f0f0f0f & x ) + ( 0x0f0f0f0f & ( x >> 4 ) );
       x = ( 0x00ff00ff & x ) + ( 0x00ff00ff & ( x >> 8 ) );
       x = ( 0x0000ffff & x ) + ( 0x0000ffff & ( x >> 16 ) );
    
       return x;
    }
    -Prelude
    My best code is written with the delete key.

  5. #5
    moi
    moi is offline
    Registered User moi's Avatar
    Join Date
    Jul 2002
    Posts
    946
    oh that's just disgusting
    hello, internet!

  6. #6
    Skunkmeister Stoned_Coder's Avatar
    Join Date
    Aug 2001
    Posts
    2,572
    I think id loop thru the bits.Why would you not want to? Salems look up table of 256 is workable but you would still need some calculations done adding the four bytes set bit counts together.
    Preludes example tho clever is a maintainence programmers nightmare with hex numbers and shifts and no comments to help you see what the original programmer intended.It is not really self-documenting so should be commented.
    Free the weed!! Class B to class C is not good enough!!
    And the FAQ is here :- http://faq.cprogramming.com/cgi-bin/smartfaq.cgi

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. bintree and count (withouth using template)?
    By cubimongoloid in forum C++ Programming
    Replies: 7
    Last Post: 05-24-2009, 07:22 AM
  2. SDLKey to ASCII without unicode support?
    By zacs7 in forum Game Programming
    Replies: 6
    Last Post: 10-07-2007, 04:03 AM
  3. input question
    By piyush_v in forum C Programming
    Replies: 9
    Last Post: 04-12-2007, 08:09 AM
  4. Please Explain Count the number of bits in an int code
    By dnysveen in forum C++ Programming
    Replies: 36
    Last Post: 12-23-2006, 10:39 PM
  5. Program Crashing
    By Pressure in forum C Programming
    Replies: 3
    Last Post: 04-18-2005, 11:28 PM

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