Q, 1 counting and memory usage

[Hur]

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

[dandelion]

"Hur" <ja**********@y ahoo.com> wrote in message
news:ct******** **@delphi.et.tu delft.nl...

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;
}

[infobahn]

dandelion wrote:

"Hur" <ja**********@y ahoo.com> wrote in message
news:ct******** **@delphi.et.tu delft.nl...

- 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.

[dandelion]

"infobahn" <in******@btint ernet.com> wrote in message
news:42******** *******@btinter net.com...

dandelion wrote:

"Hur" <ja**********@y ahoo.com> wrote in message
news:ct******** **@delphi.et.tu delft.nl...

- 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.

[Jonathan Burd]

dandelion wrote:

"Hur" <ja**********@y ahoo.com> wrote in message
news:ct******** **@delphi.et.tu delft.nl...

<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

[dandelion]

"Jonathan Burd" <jb***@nospam.c om> wrote in message
news:36******** *****@individua l.net...
<snip>

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

cnt++;
value >>= 1;

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

Correct, of course.

[Chris Croughton]

On Wed, 2 Feb 2005 11:42:03 +0100, dandelion
<da*******@mead ow.net> wrote:

"Hur" <ja**********@y ahoo.com> wrote in message
news:ct******** **@delphi.et.tu delft.nl...

- 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(unsi gned long value)
{
int cnt = 0;
while (value)
{
++cnt;
value &= value - 1;
}
return cnt;
}

Although one could do it recursively:

int count_ones(unsi gned long value)
{
return 1 + count_ones(valu e & (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

[Michael Mair]

Chris Croughton wrote:

On Wed, 2 Feb 2005 11:42:03 +0100, dandelion
<da*******@mead ow.net> wrote:

"Hur" <ja**********@y ahoo.com> wrote in message
news:ct****** ****@delphi.et. tudelft.nl...

- 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_va lue
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(unsi gned long value)
{
int cnt = 0;
while (value)
{
++cnt;
value &= value - 1;
}
return cnt;
}

Although one could do it recursively:

int count_ones(unsi gned long value)
{
return 1 + count_ones(valu e & (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.

[CBFalconer]

dandelion wrote:

"Jonathan Burd" <jb***@nospam.c om> 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.c om, 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

[Peteris Krumins]

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