Q, 1 counting and memory usage

H

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
 
D

dandelion

Hur said:
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;
}
 
I

infobahn

dandelion said:
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.
 
D

dandelion

infobahn said:
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.
 
C

Chris Croughton

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
 
M

Michael Mair

Chris said:
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
 
C

CBFalconer

dandelion said:
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 :)
 
P

Peteris Krumins

Hur said:
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
 
C

Christian Bau

"Peteris Krumins said:
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))


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.
 

Ask a Question

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

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

No members online now.

Forum statistics

Threads
473,744
Messages
2,569,483
Members
44,903
Latest member
orderPeak8CBDGummies

Latest Threads

Top