Q, 1 counting and memory usage

Discussion in 'C Programming' started by Hur, Feb 2, 2005.

  1. Hur

    Hur Guest

    hi i ask two questions......someone can tell me

    i an a linux gcc user and wanna know that

    - how much physical memory is used for my c code ?

    and another one is

    - i need a (standard) function to count the number of '1'
    for example,
    1010 1000 0000 0000 ====> 3
    0000 0000 1111 0000 ====> 4
     
    Hur, Feb 2, 2005
    #1
    1. Advertising

  2. Hur

    dandelion Guest

    "Hur" <> wrote in message
    news:ctqa43$vh4$...
    > hi i ask two questions......someone can tell me
    >
    > i an a linux gcc user and wanna know that
    >
    > - how much physical memory is used for my c code ?


    Depends on the program. Without you C-code, your compiler, the setting of
    that compiler, it is simply impossible to tell. gcc -O3 will produce a
    different number than gcc -Os, for instance, and the results will be
    different depending for an i386 and an Atmel AVR.

    > - i need a (standard) function to count the number of '1'
    > for example,
    > 1010 1000 0000 0000 ====> 3
    > 0000 0000 1111 0000 ====> 4


    That's not hard.

    int count_ones(int value)
    {
    int cnt = 0;

    while(value != 0)
    {
    if (0 != (cnt & 1))
    cnt++;
    value >>= 1;
    }

    return cnt;
    }
     
    dandelion, Feb 2, 2005
    #2
    1. Advertising

  3. Hur

    infobahn Guest

    dandelion wrote:
    >
    > "Hur" <> wrote in message
    > news:ctqa43$vh4$...
    >
    > > - i need a (standard) function to count the number of '1'
    > > for example,
    > > 1010 1000 0000 0000 ====> 3
    > > 0000 0000 1111 0000 ====> 4

    >
    > That's not hard.
    >
    > int count_ones(int value)
    > {
    > int cnt = 0;
    >
    > while(value != 0)
    > {
    > if (0 != (cnt & 1))
    > cnt++;
    > value >>= 1;
    > }
    >
    > return cnt;
    > }


    It's harder than it looks.

    printf("%d\n", count_ones(-1));

    On systems with sign bit propagation, this call could take some time.

    Consider the merits of unsigned long.
     
    infobahn, Feb 2, 2005
    #3
  4. Hur

    dandelion Guest

    "infobahn" <> wrote in message
    news:...
    > dandelion wrote:
    > >
    > > "Hur" <> wrote in message
    > > news:ctqa43$vh4$...
    > >
    > > > - i need a (standard) function to count the number of '1'
    > > > for example,
    > > > 1010 1000 0000 0000 ====> 3
    > > > 0000 0000 1111 0000 ====> 4

    > >
    > > That's not hard.
    > >
    > > int count_ones(int value)
    > > {
    > > int cnt = 0;
    > >
    > > while(value != 0)
    > > {
    > > if (0 != (cnt & 1))
    > > cnt++;
    > > value >>= 1;
    > > }
    > >
    > > return cnt;
    > > }

    >
    > It's harder than it looks.
    >
    > printf("%d\n", count_ones(-1));
    >
    > On systems with sign bit propagation, this call could take some time.
    >
    > Consider the merits of unsigned long.


    Shit, scheisse, merd'allors, kut met peren! Gretverdrie! ;-)

    Absolutely right, of course. Never underestimate the problem. That should
    indeed have been an unsigned int/long.
     
    dandelion, Feb 2, 2005
    #4
  5. dandelion wrote:
    > "Hur" <> wrote in message
    > news:ctqa43$vh4$...
    >


    <snip>

    >
    > That's not hard.
    >
    > int count_ones(int value)


    unsigned long value

    > {
    > int cnt = 0;
    >
    > while(value != 0)
    > {
    > if (0 != (cnt & 1))


    Should be: if (0 != (value & 1))

    > cnt++;
    > value >>= 1;


    <snip>

    Regards,
    Jonathan.


    --
    Email: "jonathan [period] burd [commercial-at] gmail [period] com" sans-WSP

    "We must do something. This is something. Therefore, we must do this."
    - Keith Thompson
     
    Jonathan Burd, Feb 2, 2005
    #5
  6. Hur

    dandelion Guest

    "Jonathan Burd" <> wrote in message
    news:...
    <snip>
    > Should be: if (0 != (value & 1))
    >
    > > cnt++;
    > > value >>= 1;


    Sigh.... The dangers of writing ad hoc code.

    Correct, of course.
     
    dandelion, Feb 2, 2005
    #6
  7. On Wed, 2 Feb 2005 11:42:03 +0100, dandelion
    <> wrote:

    > "Hur" <> wrote in message
    > news:ctqa43$vh4$...
    >
    >> - i need a (standard) function to count the number of '1'
    >> for example,
    >> 1010 1000 0000 0000 ====> 3
    >> 0000 0000 1111 0000 ====> 4

    >
    > That's not hard.
    >
    > int count_ones(int value)
    > {
    > int cnt = 0;
    >
    > while(value != 0)
    > {
    > if (0 != (cnt & 1))
    > cnt++;
    > value >>= 1;
    > }
    >
    > return cnt;
    > }


    Faster and more reliable (with negative inputs) is:

    int count_ones(unsigned long value)
    {
    int cnt = 0;
    while (value)
    {
    ++cnt;
    value &= value - 1;
    }
    return cnt;
    }

    Although one could do it recursively:

    int count_ones(unsigned long value)
    {
    return 1 + count_ones(value & (value - 1));
    }

    Or in C99 #include <stdint.h> and use uintmax_t instead of unsigned
    long, then the type will always be large enough.

    Chris C
     
    Chris Croughton, Feb 2, 2005
    #7
  8. Hur

    Michael Mair Guest

    Chris Croughton wrote:
    > On Wed, 2 Feb 2005 11:42:03 +0100, dandelion
    > <> wrote:
    >
    >
    >>"Hur" <> wrote in message
    >>news:ctqa43$vh4$...
    >>
    >>
    >>>- i need a (standard) function to count the number of '1'
    >>> for example,
    >>> 1010 1000 0000 0000 ====> 3
    >>> 0000 0000 1111 0000 ====> 4

    >>
    >>That's not hard.
    >>
    >>int count_ones(int value)
    >>{
    >> int cnt = 0;
    >>
    >> while(value != 0)
    >> {
    >> if (0 != (cnt & 1))
    >> cnt++;
    >> value >>= 1;
    >> }
    >>
    >> return cnt;
    >>}

    >
    >
    > Faster and more reliable (with negative inputs) is:


    The first is probably almost always true, the second not:
    The representation of negative_value and 0UL+negative_value
    may differ. If we have a logical right shift, the above
    (with the corrections of the others) will work correctly.
    I guess the most reliable (but not fastest) way is using
    your code with unsigned char value and run through all
    the bytes (which holds issues of its own; you essentially
    can only wrap that up in a macro if you do not want to
    prescribe a type, ...)


    Cheers
    Michael
    >
    > int count_ones(unsigned long value)
    > {
    > int cnt = 0;
    > while (value)
    > {
    > ++cnt;
    > value &= value - 1;
    > }
    > return cnt;
    > }
    >
    > Although one could do it recursively:
    >
    > int count_ones(unsigned long value)
    > {
    > return 1 + count_ones(value & (value - 1));
    > }
    >
    > Or in C99 #include <stdint.h> and use uintmax_t instead of unsigned
    > long, then the type will always be large enough.
    >
    > Chris C

    --
    E-Mail: Mine is an /at/ gmx /dot/ de address.
     
    Michael Mair, Feb 2, 2005
    #8
  9. Hur

    CBFalconer Guest

    dandelion wrote:
    > "Jonathan Burd" <> wrote in message
    >
    > <snip>
    >> Should be: if (0 != (value & 1))
    >>
    >>> cnt++;
    >>> value >>= 1;

    >
    > Sigh.... The dangers of writing ad hoc code.
    >
    > Correct, of course.


    Now, what is left to go wrong. Surely we can find another gaping
    hole in the original code :)

    --
    "If you want to post a followup via groups.google.com, don't use
    the broken "Reply" link at the bottom of the article. Click on
    "show options" at the top of the article, then click on the
    "Reply" at the bottom of the article headers." - Keith Thompson
     
    CBFalconer, Feb 2, 2005
    #9
  10. Hur wrote:
    > hi i ask two questions......someone can tell me
    >
    > i an a linux gcc user and wanna know that
    >
    > - how much physical memory is used for my c code ?
    >


    As your C code gets compiled into assembler code and then
    into machine code, and as the program gets loaded into memory,
    the size of your c code == size of the machine code == size of .text
    segment of your program + ((size of the machine code) mod (memory
    alignment))

    > and another one is
    >
    > - i need a (standard) function to count the number of '1'
    > for example,
    > 1010 1000 0000 0000 ====> 3
    > 0000 0000 1111 0000 ====> 4


    No such thing as standard way for counting number of 1 bits in byte.

    Here is nice way:

    int
    cb(unsigned x)
    {
    x = (x & 0x55555555) + ((x >> 1) & 0x55555555);
    x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
    x = (x & 0x0f0f0f0f) + ((x >> 4) & 0x0f0f0f0f);
    x = (x & 0x00ff00ff) + ((x >> 8) & 0x00ff00ff);
    x = (x & 0x0000ffff) + ((x >> 16) & 0x0000ffff);
    return x;
    }


    P.Krumins
     
    Peteris Krumins, Feb 3, 2005
    #10
  11. In article <>,
    "Peteris Krumins" <> wrote:

    > Hur wrote:
    > > hi i ask two questions......someone can tell me
    > >
    > > i an a linux gcc user and wanna know that
    > >
    > > - how much physical memory is used for my c code ?
    > >

    >
    > As your C code gets compiled into assembler code and then
    > into machine code, and as the program gets loaded into memory,
    > the size of your c code == size of the machine code == size of .text
    > segment of your program + ((size of the machine code) mod (memory
    > alignment))
    >
    > > and another one is
    > >
    > > - i need a (standard) function to count the number of '1'
    > > for example,
    > > 1010 1000 0000 0000 ====> 3
    > > 0000 0000 1111 0000 ====> 4

    >
    > No such thing as standard way for counting number of 1 bits in byte.
    >
    > Here is nice way:
    >
    > int
    > cb(unsigned x)
    > {
    > x = (x & 0x55555555) + ((x >> 1) & 0x55555555);
    > x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
    > x = (x & 0x0f0f0f0f) + ((x >> 4) & 0x0f0f0f0f);
    > x = (x & 0x00ff00ff) + ((x >> 8) & 0x00ff00ff);
    > x = (x & 0x0000ffff) + ((x >> 16) & 0x0000ffff);
    > return x;
    > }


    Undefined behavior when unsigned int has 16 bits. Wrong result when
    unsigned int has more than 32 bits.
     
    Christian Bau, Feb 3, 2005
    #11
  12. Sure.


    P.Krumins
     
    Peteris Krumins, Feb 3, 2005
    #12
    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. metfan
    Replies:
    2
    Views:
    4,853
    Robert Olofsson
    Oct 21, 2003
  2. hvt
    Replies:
    0
    Views:
    1,215
  3. hvt
    Replies:
    0
    Views:
    1,477
  4. Krist
    Replies:
    8
    Views:
    6,494
    Arne Vajhøj
    Feb 10, 2010
  5. edwardfredriks

    counting up instead of counting down

    edwardfredriks, Sep 6, 2005, in forum: Javascript
    Replies:
    6
    Views:
    207
    Dr John Stockton
    Sep 7, 2005
Loading...

Share This Page