number of 1's in a byte

This is a discussion on number of 1's in a byte within the C Programming forums, part of the General Programming Boards category; Hi all how to count number of 1's in a byte. please explain me about this. any help it should ...

  1. #1
    Registered User
    Join Date
    Dec 2006
    Posts
    136

    number of 1's in a byte

    Hi all
    how to count number of 1's in a byte.
    please explain me about this.

    any help it should be appreciable

  2. #2
    Woof, woof! zacs7's Avatar
    Join Date
    Mar 2007
    Location
    Australia
    Posts
    3,459
    There are a few ways, perhaps the easiest is:

    1. shift
    2. AND
    3. repeat CHAR_BITS times
    Last edited by zacs7; 10-13-2008 at 05:39 AM.

  3. #3
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    If you want to do it OFTEN, and you KNOW that a byte is always 8 bits, you could use a table - most efficient is probably a table for 4 bits at a time. This makes it two lookups and one shift, instead of (say) 8 shifts.

    Of course, a char or byte is not necessarily 8 bits - although hardware with other varieties is quite rare, it's worth considering if you want highly portable code.

    --
    Mats
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  4. #4
    Technical Lead QuantumPete's Avatar
    Join Date
    Aug 2007
    Location
    London, UK
    Posts
    894
    We actually ask this as an interview question. Assuming you have an 8 bit char, you can use a 256 element lookup table.

    QuantumPete
    "No-one else has reported this problem, you're either crazy or a liar" - Dogbert Technical Support
    "Have you tried turning it off and on again?" - The IT Crowd

  5. #5
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    Quote Originally Posted by QuantumPete View Post
    We actually ask this as an interview question. Assuming you have an 8 bit char, you can use a 256 element lookup table.

    QuantumPete
    Yes, that would be the fastest method, but in some cases, using a bigger table will reduce the chances of hitting in the cache - a 16 entry table will fit in one or two cache-lines. [But if it's frequent enough, using a bigger table will be quicker].

    --
    Mats
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  6. #6
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    Quote Originally Posted by QuantumPete View Post
    We actually ask this as an interview question. Assuming you have an 8 bit char, you can use a 256 element lookup table.

    QuantumPete
    It's also one of the C examples used in the wikipedia entry for "lookup table", as is matsp's point about cacheing.
    C programming resources:
    GNU C Function and Macro Index -- glibc reference manual
    The C Book -- nice online learner guide
    Current ISO draft standard
    CCAN -- new CPAN like open source library repository
    3 (different) GNU debugger tutorials: #1 -- #2 -- #3
    cpwiki -- our wiki on sourceforge

  7. #7
    Chinese pâté foxman's Avatar
    Join Date
    Jul 2007
    Location
    Canada
    Posts
    404
    Quote Originally Posted by QuantumPete View Post
    We actually ask this as an interview question. Assuming you have an 8 bit char, you can use a 256 element lookup table.
    But then, the question becomes: how do you build such a table ?
    I hate real numbers.

  8. #8
    Registered User
    Join Date
    Sep 2008
    Location
    Toronto, Canada
    Posts
    1,831
    I guess at some point you need to shift a 1-bit mask through the integer like any naive algorithm would do. Unless you are intimating there may be a mathematical shortcut. Damn now I'll have to research it further. I love puzzles.

    Oh, darn, it's already solved to death.
    http://gurmeetsingh.wordpress.com/20...ting-routines/
    and
    http://en.wikipedia.org/wiki/Hamming_weight
    Last edited by nonoob; 10-13-2008 at 02:28 PM.

  9. #9
    Banned master5001's Avatar
    Join Date
    Aug 2001
    Location
    Visalia, CA, USA
    Posts
    3,685
    Example:
    Code:
    union sub_optimal_solution
    {
      struct
      {
        unsigned char bit0 : 1;
        unsigned char bit1 : 1;
        unsigned char bit2 : 1;
        unsigned char bit3 : 1;
        unsigned char bit4 : 1;
        unsigned char bit5 : 1;
        unsigned char bit6 : 1;
        unsigned char bit7 : 1;
      };
    
      unsigned char all;
    };
    
    /* The above uses some non-standard extentions that are safe with GCC and MSVC */
    int bitCount(char x)
    {
      union sub_optimal_solution y;
    
      y.all = x;
    
      return y.bit0 + y.bit1 + y.bit2 + y.bit3 + y.bit4 + y.bit5 + y.bit6 + y.bit7;
    }
    Is this a good way of doing this? Hells nah! Does it work? As long as your compiler can compile it.
    Last edited by master5001; 10-13-2008 at 06:18 PM.

  10. #10
    Registered User
    Join Date
    Sep 2008
    Location
    Toronto, Canada
    Posts
    1,831
    Yeah but wouldn't that be just as efficient (or not) as
    Code:
    return y.bit0 + y.bit1 + y.bit2 + y.bit3 + y.bit4 + y.bit5 + y.bit6 + y.bit7
    with no questions asked.

  11. #11
    Banned master5001's Avatar
    Join Date
    Aug 2001
    Location
    Visalia, CA, USA
    Posts
    3,685
    Touche

  12. #12
    Registered User
    Join Date
    Oct 2008
    Location
    TX
    Posts
    2,047
    What about the age old method of converting decimal to binary by repeated division as in
    Code:
    #include <stdio.h>
    
    int main(void)
    {
        unsigned char bc, rem;
        unsigned char quot = 123;
        printf("num of bits in %d ", quot);
        while (quot) {
            if ((rem = (quot % 2)) == 1)
                ++bc;
            quot /= 2;
        }
        printf ("is %d\n", bc);
    }

  13. #13
    Banned master5001's Avatar
    Join Date
    Aug 2001
    Location
    Visalia, CA, USA
    Posts
    3,685
    Luckily any modern compiler would just automatically convert all of that to bit shifts and bitwise ANDs.

  14. #14
    Registered User
    Join Date
    Oct 2008
    Location
    TX
    Posts
    2,047
    Quote Originally Posted by master5001 View Post
    Luckily any modern compiler would just automatically convert all of that to bit shifts and bitwise ANDs.
    Yes and the C bitwise operators would be lot faster as there's a 1-to-1 map between them and the machine code generated as those instructions are built into almost all micros.
    Code:
    #include <stdio.h>
    
    int main(void)
    {
        unsigned char bc, rem;
        unsigned char quot = 132;
        printf("num of bits in %d ", quot);
        while (quot) {
            if ((rem = (quot & 1)) == 1)
                ++bc;
            quot >>= 1;
        }
        printf ("is %d\n", bc);
    }

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. xor linked list
    By adramalech in forum C Programming
    Replies: 23
    Last Post: 10-14-2008, 10:13 AM
  2. Issue w/ Guess My Number Program
    By mkylman in forum C++ Programming
    Replies: 5
    Last Post: 08-23-2007, 01:31 AM
  3. Random number + guessing game trouble
    By Ravens'sWrath in forum C Programming
    Replies: 16
    Last Post: 05-08-2007, 03:33 AM
  4. Stone Age Rumble
    By KONI in forum Contests Board
    Replies: 30
    Last Post: 04-02-2007, 09:53 PM
  5. Bitwise OR
    By tinkerbell20 in forum C++ Programming
    Replies: 4
    Last Post: 06-11-2005, 02:23 AM

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