Count number of bits set in a number

Discussion in 'C Programming' started by Mack, Sep 27, 2007.

  1. Mack

    Mack Guest

    Hi all,
    I want to write a program to count number of bits set in a number.
    The condition is we should not loop through each bit to find whether
    its set or not.

    Thanks in advance,

    -Mukesh
    Mack, Sep 27, 2007
    #1
    1. Advertising

  2. "Mack" <> schrieb im Newsbeitrag
    news:...
    > Hi all,
    > I want to write a program to count number of bits set in a number.
    > The condition is we should not loop through each bit to find whether
    > its set or not.

    You'd better do your homework yourself.

    Bye, Jojo
    Joachim Schmitz, Sep 27, 2007
    #2
    1. Advertising

  3. Mack

    Eric Sosman Guest

    Mack wrote:
    > Hi all,
    > I want to write a program to count number of bits set in a number.
    > The condition is we should not loop through each bit to find whether
    > its set or not.


    Start by writing down a few numbers along with
    their bit counts, using any method you like to count
    the bits:

    Number Bits
    0 0
    1 1
    2 1
    3 2

    Now find the straight line that gives the best
    least-squares fit to the observed data (any spreadsheet
    will do this for you if you can't recall the math).
    Take the fitted coefficients and write your function:

    double bit_count(int number) {
    return 0.6 * number + 0.1;
    }

    Use more data points, if you like, to get a statistically
    more accurate fit. There, that wasn't so hard, was it?

    --
    Eric Sosman
    lid
    Eric Sosman, Sep 27, 2007
    #3
  4. On Sep 27, 5:48 pm, Eric Sosman <> wrote:
    > Mack wrote:
    > > Hi all,
    > > I want to write a program to count number of bits set in a number.
    > > The condition is we should not loop through each bit to find whether
    > > its set or not.

    >
    > Start by writing down a few numbers along with
    > their bit counts, using any method you like to count
    > the bits:
    >
    > Number Bits
    > 0 0
    > 1 1
    > 2 1
    > 3 2
    >
    > Now find the straight line that gives the best
    > least-squares fit to the observed data (any spreadsheet
    > will do this for you if you can't recall the math).
    > Take the fitted coefficients and write your function:
    >
    > double bit_count(int number) {
    > return 0.6 * number + 0.1;
    > }
    >
    > Use more data points, if you like, to get a statistically
    > more accurate fit. There, that wasn't so hard, was it?
    >
    > --
    > Eric Sosman
    >


    A rough idea will be like this... Just a very very high level idea.
    Not the exact algorithm for you.

    Take the number in which you want to count the bits set ,
    And the first bit, check if it is set, add it to
    your bitset counter if it is set. Move to next bit
    And the next bit, check if it is set , add it to
    your bitset counter if it is set. Move to next bit.

    Implement with bitwise operators (lshift or rshift , & ) and have fun.

    Karthik Balaguru
    karthikbalaguru, Sep 27, 2007
    #4
  5. Mack

    Mark Bluemel Guest

    karthikbalaguru wrote:
    > On Sep 27, 5:48 pm, Eric Sosman <> wrote:
    >> Mack wrote:
    >>> Hi all,
    >>> I want to write a program to count number of bits set in a number.
    >>> The condition is we should not loop through each bit to find whether
    >>> its set or not.

    [Snip]
    > A rough idea will be like this... Just a very very high level idea.
    > Not the exact algorithm for you.
    >
    > Take the number in which you want to count the bits set ,
    > And the first bit, check if it is set, add it to
    > your bitset counter if it is set. Move to next bit
    > And the next bit, check if it is set , add it to
    > your bitset counter if it is set. Move to next bit.


    What part of "we should not loop through each bit" didn't you understand?
    Mark Bluemel, Sep 27, 2007
    #5
  6. On Sep 27, 6:06 pm, Mark Bluemel <> wrote:
    > karthikbalaguru wrote:
    > > On Sep 27, 5:48 pm, Eric Sosman <> wrote:
    > >> Mack wrote:
    > >>> Hi all,
    > >>> I want to write a program to count number of bits set in a number.
    > >>> The condition is we should not loop through each bit to find whether
    > >>> its set or not.

    > [Snip]
    > > A rough idea will be like this... Just a very very high level idea.
    > > Not the exact algorithm for you.

    >
    > > Take the number in which you want to count the bits set ,
    > > And the first bit, check if it is set, add it to
    > > your bitset counter if it is set. Move to next bit
    > > And the next bit, check if it is set , add it to
    > > your bitset counter if it is set. Move to next bit.

    >
    > What part of "we should not loop through each bit" didn't you understand?- Hide quoted text -
    >
    > - Show quoted text -


    Then, do not shift the bits in the number that you are checking for
    the bits set.
    Move the other number that you are 'And'ing with.

    Something like below !
    This is a rough idea/steps, it will not compile or give the exact
    output that you desire.

    a = 0x1100;
    b = 0x0001;
    if(a & b) bitsetcount++;
    if(a & b<<1) bitsetcount++;
    if(a & b<<2) bitsetcount++;
    if(a & b<<3) bitsetcount++;

    Karthik Balaguru
    karthikbalaguru, Sep 27, 2007
    #6
  7. Mack

    Mark Bluemel Guest

    Mack wrote:
    > Hi all,
    > I want to write a program to count number of bits set in a number.


    I think you meant to say "my homework is to write ...".

    > The condition is we should not loop through each bit to find whether
    > its set or not.


    We're not going to write it for you, but a few moments with Google for
    "bit manipulation tricks" or some similar search term would be valid
    research I'd say...

    I found a wonderfully elegant solution in a matter of moments...
    Mark Bluemel, Sep 27, 2007
    #7
  8. Mack

    user923005 Guest

    On Sep 27, 12:49 am, Mack <> wrote:
    > Hi all,
    > I want to write a program to count number of bits set in a number.
    > The condition is we should not loop through each bit to find whether
    > its set or not.


    #include <limits.h>
    #include <stdlib.h>
    #include <stdio.h>
    /*
    This is from the C-FAQ:
    */

    #define BITMASK(b) (1 << ((b) % CHAR_BIT))
    #define BITSLOT(b) ((b) / CHAR_BIT)
    #define BITSET(a, b) ((a)[BITSLOT(b)] |= BITMASK(b))
    #define BITTEST(a, b) ((a)[BITSLOT(b)] & BITMASK(b))

    /*
    This is from the C-FAQ:
    */
    int rand_range(size_t n)
    {
    return (int) ((double) rand() / ((double) RAND_MAX + 1) * n);
    }

    /*
    This is decidedly *not* from the C-FAQ (but in the tradition of the
    great Peter Seebach, I present to you):

    In the modus operandi of 'bogo-sort', I present the {*cough*,
    drumroll..} 'nearly optimal' algorithm 'bogo-bitcount'.

    This version is for one byte unsigned integers, but easily generalizes
    to unsigned long long.

    It may need a few minor _tweaks_ to work efficiently with integers of
    64 bits or larger.

    Sample run:
    0 has 0 bits in it.
    1 has 1 bits in it.
    2 has 1 bits in it.
    3 has 2 bits in it.
    4 has 1 bits in it.
    5 has 2 bits in it.
    6 has 2 bits in it.
    7 has 3 bits in it.
    8 has 1 bits in it.
    9 has 2 bits in it.
    10 has 2 bits in it.
    11 has 3 bits in it.
    12 has 2 bits in it.
    13 has 3 bits in it.
    14 has 3 bits in it.
    15 has 4 bits in it.
    16 has 1 bits in it.
    17 has 2 bits in it.
    18 has 2 bits in it.
    19 has 3 bits in it.
    20 has 2 bits in it.
    21 has 3 bits in it.
    22 has 3 bits in it.
    23 has 4 bits in it.
    24 has 2 bits in it.
    25 has 3 bits in it.
    26 has 3 bits in it.
    27 has 4 bits in it.
    28 has 3 bits in it.
    29 has 4 bits in it.
    30 has 4 bits in it.
    31 has 5 bits in it.
    32 has 1 bits in it.
    33 has 2 bits in it.
    34 has 2 bits in it.
    35 has 3 bits in it.
    36 has 2 bits in it.
    37 has 3 bits in it.
    38 has 3 bits in it.
    39 has 4 bits in it.
    40 has 2 bits in it.
    41 has 3 bits in it.
    42 has 3 bits in it.
    43 has 4 bits in it.
    44 has 3 bits in it.
    45 has 4 bits in it.
    46 has 4 bits in it.
    47 has 5 bits in it.
    48 has 2 bits in it.
    49 has 3 bits in it.
    50 has 3 bits in it.
    51 has 4 bits in it.
    52 has 3 bits in it.
    53 has 4 bits in it.
    54 has 4 bits in it.
    55 has 5 bits in it.
    56 has 3 bits in it.
    57 has 4 bits in it.
    58 has 4 bits in it.
    59 has 5 bits in it.
    60 has 4 bits in it.
    61 has 5 bits in it.
    62 has 5 bits in it.
    63 has 6 bits in it.
    64 has 1 bits in it.
    65 has 2 bits in it.
    66 has 2 bits in it.
    67 has 3 bits in it.
    68 has 2 bits in it.
    69 has 3 bits in it.
    70 has 3 bits in it.
    71 has 4 bits in it.
    72 has 2 bits in it.
    73 has 3 bits in it.
    74 has 3 bits in it.
    75 has 4 bits in it.
    76 has 3 bits in it.
    77 has 4 bits in it.
    78 has 4 bits in it.
    79 has 5 bits in it.
    80 has 2 bits in it.
    81 has 3 bits in it.
    82 has 3 bits in it.
    83 has 4 bits in it.
    84 has 3 bits in it.
    85 has 4 bits in it.
    86 has 4 bits in it.
    87 has 5 bits in it.
    88 has 3 bits in it.
    89 has 4 bits in it.
    90 has 4 bits in it.
    91 has 5 bits in it.
    92 has 4 bits in it.
    93 has 5 bits in it.
    94 has 5 bits in it.
    95 has 6 bits in it.
    96 has 2 bits in it.
    97 has 3 bits in it.
    98 has 3 bits in it.
    99 has 4 bits in it.
    100 has 3 bits in it.
    101 has 4 bits in it.
    102 has 4 bits in it.
    103 has 5 bits in it.
    104 has 3 bits in it.
    105 has 4 bits in it.
    106 has 4 bits in it.
    107 has 5 bits in it.
    108 has 4 bits in it.
    109 has 5 bits in it.
    110 has 5 bits in it.
    111 has 6 bits in it.
    112 has 3 bits in it.
    113 has 4 bits in it.
    114 has 4 bits in it.
    115 has 5 bits in it.
    116 has 4 bits in it.
    117 has 5 bits in it.
    118 has 5 bits in it.
    119 has 6 bits in it.
    120 has 4 bits in it.
    121 has 5 bits in it.
    122 has 5 bits in it.
    123 has 6 bits in it.
    124 has 5 bits in it.
    125 has 6 bits in it.
    126 has 6 bits in it.
    127 has 7 bits in it.
    128 has 1 bits in it.
    129 has 2 bits in it.
    130 has 2 bits in it.
    131 has 3 bits in it.
    132 has 2 bits in it.
    133 has 3 bits in it.
    134 has 3 bits in it.
    135 has 4 bits in it.
    136 has 2 bits in it.
    137 has 3 bits in it.
    138 has 3 bits in it.
    139 has 4 bits in it.
    140 has 3 bits in it.
    141 has 4 bits in it.
    142 has 4 bits in it.
    143 has 5 bits in it.
    144 has 2 bits in it.
    145 has 3 bits in it.
    146 has 3 bits in it.
    147 has 4 bits in it.
    148 has 3 bits in it.
    149 has 4 bits in it.
    150 has 4 bits in it.
    151 has 5 bits in it.
    152 has 3 bits in it.
    153 has 4 bits in it.
    154 has 4 bits in it.
    155 has 5 bits in it.
    156 has 4 bits in it.
    157 has 5 bits in it.
    158 has 5 bits in it.
    159 has 6 bits in it.
    160 has 2 bits in it.
    161 has 3 bits in it.
    162 has 3 bits in it.
    163 has 4 bits in it.
    164 has 3 bits in it.
    165 has 4 bits in it.
    166 has 4 bits in it.
    167 has 5 bits in it.
    168 has 3 bits in it.
    169 has 4 bits in it.
    170 has 4 bits in it.
    171 has 5 bits in it.
    172 has 4 bits in it.
    173 has 5 bits in it.
    174 has 5 bits in it.
    175 has 6 bits in it.
    176 has 3 bits in it.
    177 has 4 bits in it.
    178 has 4 bits in it.
    179 has 5 bits in it.
    180 has 4 bits in it.
    181 has 5 bits in it.
    182 has 5 bits in it.
    183 has 6 bits in it.
    184 has 4 bits in it.
    185 has 5 bits in it.
    186 has 5 bits in it.
    187 has 6 bits in it.
    188 has 5 bits in it.
    189 has 6 bits in it.
    190 has 6 bits in it.
    191 has 7 bits in it.
    192 has 2 bits in it.
    193 has 3 bits in it.
    194 has 3 bits in it.
    195 has 4 bits in it.
    196 has 3 bits in it.
    197 has 4 bits in it.
    198 has 4 bits in it.
    199 has 5 bits in it.
    200 has 3 bits in it.
    201 has 4 bits in it.
    202 has 4 bits in it.
    203 has 5 bits in it.
    204 has 4 bits in it.
    205 has 5 bits in it.
    206 has 5 bits in it.
    207 has 6 bits in it.
    208 has 3 bits in it.
    209 has 4 bits in it.
    210 has 4 bits in it.
    211 has 5 bits in it.
    212 has 4 bits in it.
    213 has 5 bits in it.
    214 has 5 bits in it.
    215 has 6 bits in it.
    216 has 4 bits in it.
    217 has 5 bits in it.
    218 has 5 bits in it.
    219 has 6 bits in it.
    220 has 5 bits in it.
    221 has 6 bits in it.
    222 has 6 bits in it.
    223 has 7 bits in it.
    224 has 3 bits in it.
    225 has 4 bits in it.
    226 has 4 bits in it.
    227 has 5 bits in it.
    228 has 4 bits in it.
    229 has 5 bits in it.
    230 has 5 bits in it.
    231 has 6 bits in it.
    232 has 4 bits in it.
    233 has 5 bits in it.
    234 has 5 bits in it.
    235 has 6 bits in it.
    236 has 5 bits in it.
    237 has 6 bits in it.
    238 has 6 bits in it.
    239 has 7 bits in it.
    240 has 4 bits in it.
    241 has 5 bits in it.
    242 has 5 bits in it.
    243 has 6 bits in it.
    244 has 5 bits in it.
    245 has 6 bits in it.
    246 has 6 bits in it.
    247 has 7 bits in it.
    248 has 5 bits in it.
    249 has 6 bits in it.
    250 has 6 bits in it.
    251 has 7 bits in it.
    252 has 6 bits in it.
    253 has 7 bits in it.
    254 has 7 bits in it.
    255 has 8 bits in it.

    Enjoy this marvel of efficiency.
    */

    int bitcount_the_hard_way(unsigned char value)
    {
    unsigned char test_mask = 0;
    unsigned bitcount = 0;
    /* choose a random bit: */
    int bit;
    if (!value)
    return 0;
    morebits:
    if (test_mask == 0xff) {
    test_mask = 0; /* this set of passes did not work, try
    * again... */
    bitcount = 0;
    }
    bit = rand_range(CHAR_BIT);
    if (BITTEST(&test_mask, bit))
    goto morebits; /* If the bit is already set, choose another
    * one... */
    BITSET(&test_mask, bit);
    bitcount++;
    if ((test_mask ^ value) == 0)
    return bitcount;
    goto morebits;
    }

    int main(void)
    {
    unsigned index;
    int count;
    for (index = 0; index <= UCHAR_MAX; index++) {
    count = bitcount_the_hard_way(index);
    printf("%u has %d bits in it.\n", index, count);
    }
    return 0;
    }
    user923005, Sep 27, 2007
    #8
  9. Mack

    pete Guest

    Mark Bluemel wrote:
    >
    > karthikbalaguru wrote:
    > > On Sep 27, 5:48 pm, Eric Sosman <> wrote:
    > >> Mack wrote:
    > >>> Hi all,
    > >>> I want to write a program to
    > >>> count number of bits set in a number.
    > >>> The condition is we should not loop
    > >>> through each bit to find whether its set or not.

    > [Snip]
    > > A rough idea will be like this... Just a very very high level idea.
    > > Not the exact algorithm for you.
    > >
    > > Take the number in which you want to count the bits set ,
    > > And the first bit, check if it is set, add it to
    > > your bitset counter if it is set. Move to next bit
    > > And the next bit, check if it is set , add it to
    > > your bitset counter if it is set. Move to next bit.

    >
    > What part of "we should not loop through each bit"
    > didn't you understand?


    I had trouble understanding it.
    Is it allowable to only loop through the set bits
    if you don't loop through the unset bits?

    unsigned bit_count(unsigned n)
    {
    unsigned count;

    for (count = 0; n != 0; n &= n - 1) {
    ++count;
    }
    return count;
    }

    --
    pete
    pete, Sep 27, 2007
    #9
  10. Mack

    user923005 Guest

    On Sep 27, 3:44 pm, pete <> wrote:
    > Mark Bluemel wrote:
    >
    > > karthikbalaguru wrote:
    > > > On Sep 27, 5:48 pm, Eric Sosman <> wrote:
    > > >> Mack wrote:
    > > >>> Hi all,
    > > >>> I want to write a program to
    > > >>> count number of bits set in a number.
    > > >>> The condition is we should not loop
    > > >>> through each bit to find whether its set or not.

    > > [Snip]
    > > > A rough idea will be like this... Just a very very high level idea.
    > > > Not the exact algorithm for you.

    >
    > > > Take the number in which you want to count the bits set ,
    > > > And the first bit, check if it is set, add it to
    > > > your bitset counter if it is set. Move to next bit
    > > > And the next bit, check if it is set , add it to
    > > > your bitset counter if it is set. Move to next bit.

    >
    > > What part of "we should not loop through each bit"
    > > didn't you understand?

    >
    > I had trouble understanding it.
    > Is it allowable to only loop through the set bits
    > if you don't loop through the unset bits?
    >
    > unsigned bit_count(unsigned n)
    > {
    > unsigned count;
    >
    > for (count = 0; n != 0; n &= n - 1) {
    > ++count;
    > }
    > return count;
    >
    > }


    The algorithm I posted is intended to be mind-numbingly stupid.

    It sets random bits in a string, one at a time (until potentially all
    bits are set).

    Then, after each bit is set, it does an xor to see if the current
    number matches the number passed in.

    If the numbers match, then return the number of bits set.

    Otherwise continue setting bits until all bits are set.

    If all bits are set and we did not find a match, then reset to zero
    and try again.

    It is conceivable that the value 1 would iterate forever, but most
    likely it would only take about 4 full passes through the code (on
    average) to find a match. A bad prng could spell real trouble here,
    especially if you extend it to larger integer sizes.

    I suggest that a contest to create a worse algorithm would require
    some hefty creativity, if there were a requirement that every
    statement must have a purpose towards the goal (e.g. no deliberate
    wait loops or things of that nature). I suppose that an incredibly
    inefficient prng might be a nice touch.
    user923005, Sep 28, 2007
    #10
  11. On Thu, 27 Sep 2007 07:49:01 -0000, Mack <>
    wrote:

    >Hi all,
    > I want to write a program to count number of bits set in a number.
    >The condition is we should not loop through each bit to find whether
    >its set or not.
    >


    Move the number into an appropriately sized array of unsigned char.
    Loop through each element of the array and use a 256 (usually) element
    lookup table to determine the number of bits in that char. Accumulate
    the sum of these bit counts over the elements.


    Remove del for email
    Barry Schwarz, Sep 28, 2007
    #11
  12. On Sep 28, 1:29 am, user923005 <> wrote:
    > On Sep 27, 12:49 am, Mack <> wrote:
    >
    > > Hi all,
    > > I want to write a program to count number of bits set in a number.
    > > The condition is we should not loop through each bit to find whether
    > > its set or not.

    >
    > #include <limits.h>
    > #include <stdlib.h>
    > #include <stdio.h>
    > /*
    > This is from the C-FAQ:
    > */
    >
    > #define BITMASK(b) (1 << ((b) % CHAR_BIT))
    > #define BITSLOT(b) ((b) / CHAR_BIT)
    > #define BITSET(a, b) ((a)[BITSLOT(b)] |= BITMASK(b))
    > #define BITTEST(a, b) ((a)[BITSLOT(b)] & BITMASK(b))
    >
    > /*
    > This is from the C-FAQ:
    > */
    > int rand_range(size_t n)
    > {
    > return (int) ((double) rand() / ((double) RAND_MAX + 1) * n);
    >
    > }
    >
    > /*
    > This is decidedly *not* from the C-FAQ (but in the tradition of the
    > great Peter Seebach, I present to you):
    >
    > In the modus operandi of 'bogo-sort', I present the {*cough*,
    > drumroll..} 'nearly optimal' algorithm 'bogo-bitcount'.
    >
    > This version is for one byte unsigned integers, but easily generalizes
    > to unsigned long long.
    >
    > It may need a few minor _tweaks_ to work efficiently with integers of
    > 64 bits or larger.
    >
    > Sample run:
    > 0 has 0 bits in it.
    > 1 has 1 bits in it.
    > 2 has 1 bits in it.
    > 3 has 2 bits in it.
    > 4 has 1 bits in it.
    > 5 has 2 bits in it.
    > 6 has 2 bits in it.
    > 7 has 3 bits in it.
    > 8 has 1 bits in it.
    > 9 has 2 bits in it.
    > 10 has 2 bits in it.
    > 11 has 3 bits in it.
    > 12 has 2 bits in it.
    > 13 has 3 bits in it.
    > 14 has 3 bits in it.
    > 15 has 4 bits in it.
    > 16 has 1 bits in it.
    > 17 has 2 bits in it.
    > 18 has 2 bits in it.
    > 19 has 3 bits in it.
    > 20 has 2 bits in it.
    > 21 has 3 bits in it.
    > 22 has 3 bits in it.
    > 23 has 4 bits in it.
    > 24 has 2 bits in it.
    > 25 has 3 bits in it.
    > 26 has 3 bits in it.
    > 27 has 4 bits in it.
    > 28 has 3 bits in it.
    > 29 has 4 bits in it.
    > 30 has 4 bits in it.
    > 31 has 5 bits in it.
    > 32 has 1 bits in it.
    > 33 has 2 bits in it.
    > 34 has 2 bits in it.
    > 35 has 3 bits in it.
    > 36 has 2 bits in it.
    > 37 has 3 bits in it.
    > 38 has 3 bits in it.
    > 39 has 4 bits in it.
    > 40 has 2 bits in it.
    > 41 has 3 bits in it.
    > 42 has 3 bits in it.
    > 43 has 4 bits in it.
    > 44 has 3 bits in it.
    > 45 has 4 bits in it.
    > 46 has 4 bits in it.
    > 47 has 5 bits in it.
    > 48 has 2 bits in it.
    > 49 has 3 bits in it.
    > 50 has 3 bits in it.
    > 51 has 4 bits in it.
    > 52 has 3 bits in it.
    > 53 has 4 bits in it.
    > 54 has 4 bits in it.
    > 55 has 5 bits in it.
    > 56 has 3 bits in it.
    > 57 has 4 bits in it.
    > 58 has 4 bits in it.
    > 59 has 5 bits in it.
    > 60 has 4 bits in it.
    > 61 has 5 bits in it.
    > 62 has 5 bits in it.
    > 63 has 6 bits in it.
    > 64 has 1 bits in it.
    > 65 has 2 bits in it.
    > 66 has 2 bits in it.
    > 67 has 3 bits in it.
    > 68 has 2 bits in it.
    > 69 has 3 bits in it.
    > 70 has 3 bits in it.
    > 71 has 4 bits in it.
    > 72 has 2 bits in it.
    > 73 has 3 bits in it.
    > 74 has 3 bits in it.
    > 75 has 4 bits in it.
    > 76 has 3 bits in it.
    > 77 has 4 bits in it.
    > 78 has 4 bits in it.
    > 79 has 5 bits in it.
    > 80 has 2 bits in it.
    > 81 has 3 bits in it.
    > 82 has 3 bits in it.
    > 83 has 4 bits in it.
    > 84 has 3 bits in it.
    > 85 has 4 bits in it.
    > 86 has 4 bits in it.
    > 87 has 5 bits in it.
    > 88 has 3 bits in it.
    > 89 has 4 bits in it.
    > 90 has 4 bits in it.
    > 91 has 5 bits in it.
    > 92 has 4 bits in it.
    > 93 has 5 bits in it.
    > 94 has 5 bits in it.
    > 95 has 6 bits in it.
    > 96 has 2 bits in it.
    > 97 has 3 bits in it.
    > 98 has 3 bits in it.
    > 99 has 4 bits in it.
    > 100 has 3 bits in it.
    > 101 has 4 bits in it.
    > 102 has 4 bits in it.
    > 103 has 5 bits in it.
    > 104 has 3 bits in it.
    > 105 has 4 bits in it.
    > 106 has 4 bits in it.
    > 107 has 5 bits in it.
    > 108 has 4 bits in it.
    > 109 has 5 bits in it.
    > 110 has 5 bits in it.
    > 111 has 6 bits in it.
    > 112 has 3 bits in it.
    > 113 has 4 bits in it.
    > 114 has 4 bits in it.
    > 115 has 5 bits in it.
    > 116 has 4 bits in it.
    > 117 has 5 bits in it.
    > 118 has 5 bits in it.
    > 119 has 6 bits in it.
    > 120 has 4 bits in it.
    > 121 has 5 bits in it.
    > 122 has 5 bits in it.
    > 123 has 6 bits in it.
    > 124 has 5 bits in it.
    > 125 has 6 bits in it.
    > 126 has 6 bits in it.
    > 127 has 7 bits in it.
    > 128 has 1 bits in it.
    > 129 has 2 bits in it.
    > 130 has 2 bits in it.
    > 131 has 3 bits in it.
    > 132 has 2 bits in it.
    > 133 has 3 bits in it.
    > 134 has 3 bits in it.
    > 135 has 4 bits in it.
    > 136 has 2 bits in it.
    > 137 has 3 bits in it.
    > 138 has 3 bits in it.
    > 139 has 4 bits in it.
    > 140 has 3 bits in it.
    > 141 has 4 bits in it.
    > 142 has 4 bits in it.
    > 143 has 5 bits in it.
    > 144 has 2 bits in it.
    > 145 has 3 bits in it.
    > 146 has 3 bits in it.
    > 147 has 4 bits in it.
    > 148 has 3 bits in it.
    > 149 has 4 bits in it.
    > 150 has 4 bits in it.
    > 151 has 5 bits in it.
    > 152 has 3 bits in it.
    > 153 has 4 bits in it.
    > 154 has 4 bits in it.
    > 155 has 5 bits in it.
    > 156 has 4 bits in it.
    > 157 has 5 bits in it.
    > 158 has 5 bits in it.
    > 159 has 6 bits in it.
    > 160 has 2 bits in it.
    > 161 has 3 bits in it.
    > 162 has 3 bits in it.
    > 163 has 4 bits in it.
    > 164 has 3 bits in it.
    > 165 has 4 bits in it.
    > 166 has 4 bits in it.
    > 167 has 5 bits in it.
    > 168 has 3 bits in it.
    > 169 has 4 bits in it.
    > 170 has 4 bits in it.
    > 171 has 5 bits in it.
    > 172 has 4 bits in it.
    > 173 has 5 bits in it.
    > 174 has 5 bits in it.
    > 175 has 6 bits in it.
    > 176 has 3 bits in it.
    > 177 has 4 bits in it.
    > 178 has 4 bits in it.
    > 179 has 5 bits in it.
    > 180 has 4 bits in it.
    > 181 has 5 bits in it.
    > 182 has 5 bits in it.
    > 183 has 6 bits in it.
    > 184 has 4 bits in it.
    > 185 has 5 bits in it.
    > 186 has 5 bits in it.
    > 187 has 6 bits in it.
    > 188 has 5 bits in it.
    > 189 has 6 bits in it.
    > 190 has 6 bits in it.
    > 191 has 7 bits in it.
    > 192 has 2 bits in it.
    > 193 has 3 bits in it.
    > 194 has 3 bits in it.
    > 195 has 4 bits in it.
    > 196 has 3 bits in it.
    > 197 has 4 bits in it.
    > 198 has 4 bits in it.
    > 199 has 5 bits in it.
    > 200 has 3 bits in it.
    > 201 has 4 bits in it.
    > 202 has 4 bits in it.
    > 203 has 5 bits in it.
    > 204 has 4 bits in it.
    > 205 has 5 bits in it.
    > 206 has 5 bits in it.
    > 207 has 6 bits in it.
    > 208 has 3 bits in it.
    > 209 has 4 bits in it.
    > 210 has 4 bits in it.
    > 211 has 5 bits in it.
    > 212 has 4 bits in it.
    > 213 has 5 bits in it.
    > 214 has 5 bits in it.
    > 215 has 6 bits in it.
    > 216 has 4 bits in it.
    > 217 has 5 bits in it.
    > 218 has 5 bits in it.
    > 219 has 6 bits in it.
    > 220 has 5 bits in it.
    > 221 has 6 bits in it.
    > 222 has 6 bits in it.
    > 223 has 7 bits in it.
    > 224 has 3 bits in it.
    > 225 has 4 bits in it.
    > 226 has 4 bits in it.
    > 227 has 5 bits in it.
    > 228 has 4 bits in it.
    > 229 has 5 bits in it.
    > 230 has 5 bits in it.
    > 231 has 6 bits in it.
    > 232 has 4 bits in it.
    > 233 has 5 bits in it.
    > 234 has 5 bits in it.
    > 235 has 6 bits in it.
    > 236 has 5 bits in it.
    > 237 has 6 bits in it.
    > 238 has 6 bits in it.
    > 239 has 7 bits in it.
    > 240 has 4 bits in it.
    > 241 has 5 bits in it.
    > 242 has 5 bits in it.
    > 243 has 6 bits in it.
    > 244 has 5 bits in it.
    > 245 has 6 bits in it.
    > 246 has 6 bits in it.
    > 247 has 7 bits in it.
    > 248 has 5 bits in it.
    > 249 has 6 bits in it.
    > 250 has 6 bits in it.
    > 251 has 7 bits in it.
    > 252 has 6 bits in it.
    > 253 has 7 bits in it.
    > 254 has 7 bits in it.
    > 255 has 8 bits in it.
    >
    > Enjoy this marvel of efficiency.
    > */
    >
    > int bitcount_the_hard_way(unsigned char value)
    > {
    > unsigned char test_mask = 0;
    > unsigned bitcount = 0;
    > /* choose a random bit: */
    > int bit;
    > if (!value)
    > return 0;
    > morebits:
    > if (test_mask == 0xff) {
    > test_mask = 0; /* this set of passes did not work, try
    > * again... */
    > bitcount = 0;
    > }
    > bit = rand_range(CHAR_BIT);
    > if (BITTEST(&test_mask, bit))
    > goto morebits; /* If the bit is already set, choose another
    > * one... */
    > BITSET(&test_mask, bit);
    > bitcount++;
    > if ((test_mask ^ value) == 0)
    > return bitcount;
    > goto morebits;
    >
    > }
    >
    > int main(void)
    > {
    > unsigned index;
    > int count;
    > for (index = 0; index <= UCHAR_MAX; index++) {
    > count = bitcount_the_hard_way(index);
    > printf("%u has %d bits in it.\n", index, count);
    > }
    > return 0;
    >
    >
    >
    > }- Hide quoted text -
    >
    > - Show quoted text -


    Mapping a Lookup Table that defines the number of bits set for every
    number and using function pointers can also help.

    Karthik Balaguru
    karthikbalaguru, Sep 28, 2007
    #12
  13. Mack

    Mark Bluemel Guest

    karthikbalaguru wrote:
    [Huge amount of irrelevant quoting snipped]
    >
    > Mapping a Lookup Table that defines the number of bits set for every
    > number and using function pointers can also help.


    You learning to edit your responses would help a lot...
    Mark Bluemel, Sep 28, 2007
    #13
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. sarmin kho
    Replies:
    2
    Views:
    816
    A. Lloyd Flanagan
    Jun 15, 2004
  2. Miki Tebeka
    Replies:
    1
    Views:
    432
    Marcin 'Qrczak' Kowalczyk
    Jun 14, 2004
  3. G Patel

    function to count number of set bits

    G Patel, Jan 29, 2005, in forum: C Programming
    Replies:
    29
    Views:
    828
  4. Vish
    Replies:
    3
    Views:
    679
    Lawrence Kirby
    Apr 29, 2005
  5. hara
    Replies:
    4
    Views:
    150
    David Squire
    May 25, 2006
Loading...

Share This Page