Well I hope he doesn't post the table!!!Originally Posted by swoopy
Not sure what he intends to do, but I think the OP's program is about as good as it gets all things considered.
Well I hope he doesn't post the table!!!Originally Posted by swoopy
Not sure what he intends to do, but I think the OP's program is about as good as it gets all things considered.
I didn't see that before I posted, anyway his code didn't look much like C++ to meOriginally Posted by Ken Fitlike
as I could understand it!!
For an entirely non-portable way:That assumes 4 byte longs.Code:long binaryCount(long number) { number = (number & 0x55555555) + ((number & 0xaaaaaaaa) >> 1); number = (number & 0x33333333) + ((number & 0xcccccccc) >> 2); number = (number & 0x0f0f0f0f) + ((number & 0xf0f0f0f0) >> 4); number = (number & 0x00ff00ff) + ((number & 0xff00ff00) >> 8); return (number & 0x0000ffff) + ((number & 0xffff0000) >> 16); }
If I did your homework for you, then you might pass your class without learning how to write a program like this. Then you might graduate and get your degree without learning how to write a program like this. You might become a professional programmer without knowing how to write a program like this. Someday you might work on a project with me without knowing how to write a program like this. Then I would have to do you serious bodily harm. - Jack Klein
This will, of course, only compile with GCC on an Alpha machine, but hey, you wanted efficient, right? No one said anything about portable.Code:int mask = ...; int count; asm("ctpop %1, %0" : "=r"(count) : "r"(mask));
All the buzzt!
CornedBee
"There is not now, nor has there ever been, nor will there ever be, any programming language in which it is the least bit difficult to write bad code."
- Flon's Law
Boring I know, but what can you do?
Whole bunch of 'em hereCode:#include <stdio.h> int main (void) { unsigned int v = 0xFF0F; unsigned int w = v - ((v >> 1) & 0x55555555); unsigned int x = (w & 0x33333333) + ((w >> 2) & 0x33333333); unsigned int c = ((x + (x >> 4) & 0xF0F0F0F) * 0x1010101) >> 24; printf ("%d\n", c); return 0; }
http://graphics.stanford.edu/~seander/bithacks.html
If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
If at first you don't succeed, try writing your phone number on the exam paper.
Damn it Salem. I get all the way to your post thinking "I've got a great link to post".
Good class architecture is not like a Swiss Army Knife; it should be more like a well balanced throwing knife.
- Mike McShaffry
Yeah I bet that was a real feat.Originally Posted by esbo
Quzah.
Hope is the first step on the road to disappointment.
Well you could change:-
to (to get rid of the 'if')Code:for ( i = 0; i < sizeof(int)*8 ; i++ ) if ( mask<<i & var) count++ ;
or evenCode:for ( i = 0; i < sizeof(int)*8 ; i++ ) count+= (mask& var>>i );
Code:for ( i = 0; i < sizeof(int)*8 ; i++, count+= (mask& var>>i ));
Nevermind. I'm slow today. All of these have already been covered probably, but if not, there ya go.
Quzah.
Last edited by quzah; 09-12-2006 at 04:43 PM.
Hope is the first step on the road to disappointment.
The fastest way I found is using lookup table. For integer, 4 bytes long, it takes 4 additional operators only.
And, this :
Also, great idea~!Code:for ( i = 0; i < sizeof(int)*8 ; i++ ) count+= (mask& var>>i );
Thanks a lot, folks.
====================
About the cross-posted, I posted this topic in C++ board first. It's wrong place for my target language, C. Then, I posted it in C board again. Sorry. Thank you, Ken Fitlike, for adding code tags.
You could even do this:
I prefer the if so I'd do:Code:int count_ones(unsigned int var) { unsigned int mask = 0x1; int count = 0; while (var != 0) { count += var & mask; var >>= 1; } return count; }
Code:int count_ones(unsigned int var) { unsigned int mask = 0x1; int count = 0; while (var != 0) { if (var & mask) count++; var >>= 1; } return count; }
I guess the fastest way would be really huge look up table, for a 32 bit int you would need
4 gigabites+ of memory though.
For a 64 bit int well, you might need a loan to buy the memory
The program might take a while to load but once loaded it would run like lightening!!
Last edited by esbo; 09-12-2006 at 05:13 PM.
Of course, you could just use, say, a 4-bit lookup table and do 8 lookups.Originally Posted by esbo
If you understand what you're doing, you're not learning anything.
You could but it would take 8 times longer to complete (at least).Originally Posted by itsme86
> You could but it would take 8 times longer to complete (at least).
Performance isn't always a problem, and this is beyond the scope of the original question.