nr of bits set to "1" in a byte

[aku]

I'm looking for the absolute fastest way
to count the nr of bits that are set to "1"
in a string. Presumably I then first need the
fastest way to do this in a byte.

I think this is it, but welcome any improvements:

i = 0;
if (g && 1) i++;
if (g && 2) i++;
if (g && 3) i++;
if (g && 4) i++;
if (g && 5) i++;
if (g && 6) i++;
if (g && 7) i++;
if (g && 8) i++;

[Ben Pfaff]

aku <ak*@europe.com > writes:

I'm looking for the absolute fastest way
to count the nr of bits that are set to "1"
in a string. Presumably I then first need the
fastest way to do this in a byte.

I think this is it, but welcome any improvements:

i = 0;
if (g && 1) i++;
if (g && 2) i++;
if (g && 3) i++;
if (g && 4) i++;
if (g && 5) i++;
if (g && 6) i++;
if (g && 7) i++;
if (g && 8) i++;

Did you try it? Not only is that probably not the fastest way,
it doesn't work.
--
Just another C hacker.

[Bertrand Mollinier Toublet]

aku wrote:

I'm looking for the absolute fastest way
to count the nr of bits that are set to "1"
in a string. Presumably I then first need the
fastest way to do this in a byte.

I think this is it, but welcome any improvements:

i = 0;
if (g && 1) i++;
if (g && 2) i++;
if (g && 3) i++;
if (g && 4) i++;
if (g && 5) i++;
if (g && 6) i++;
if (g && 7) i++;
if (g && 8) i++;

Besides Ben's accurate remark that your code will not do what you
expect, table lookup is generally considered the "absolute fastest way"
to do something. What you gain in speed, though, you lose in data size,
which is a classical tradeof. At the scale of a byte, this is still a
manageable table:

int bitsPerByte[] =
{
0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4,
1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
/* etc. I am getting lazy */
}

For any given unsigned char g, you get the number of bits set to 1 in g
with bitsPerByte[g];

--
Bertrand Mollinier Toublet
- Le top-posting.
- Quelle est la pratique la plus chiante sur Usenet ?

[Alex]

aku <ak*@europe.com > wrote:

I'm looking for the absolute fastest way
to count the nr of bits that are set to "1"
in a string. Presumably I then first need the
fastest way to do this in a byte. I think this is it, but welcome any improvements: i = 0;
if (g && 1) i++;
if (g && 2) i++;
if (g && 3) i++;
if (g && 4) i++;
if (g && 5) i++;
if (g && 6) i++;
if (g && 7) i++;
if (g && 8) i++;

Did you actually try this? It is not even close.

Even if you corrected the obvious mistake and changed
logical AND to bitwise AND (&), it is still incorrect.

Below is a 4 bit unsigned integer and the the values
that it would have if the corresponding bit was set.

[ 0 ][ 0 ][ 0 ][ 0 ]
8 4 2 1

Now, try again, preferably by using CHAR_BIT and a loop.
When you get it right, feel free to optimize.

Alex

[Stephen Mayes]

"Alex" <al*******@hotm ail.com> wrote in message
news:br******** ****@ID-190529.news.uni-berlin.de...

Now, try again, preferably by using CHAR_BIT and a loop.
When you get it right, feel free to optimize.

Alex

Can I try, please?

I've been checking this group now for two weeks and have been very much
impressed with how much I don't know about this language which I thought I
knew.
I would appreciate any critique of this code. It might not be fast, but is
it correct and will it work?

#include <stdio.h>
#include <stdlib.h> // is this required for below code ??
#include <limits.h>

int count_ones( char c )
{
int i = 0;
int count = 0;
unsigned char t = c;
unsigned char bit = 0x01; // what if CHAR_BIT != 8 ??

for( i = 0; i < CHAR_BIT; i++, bit <<= 1 ) {
if ( t & bit )
count++;
}
return count;
}

int main( void )
{
char c = (char)0; // whatever
int count = 0;

count = count_ones( c );
printf( "There are %d bits set to 1.\n", count );
return 0;
}

[Richard Heathfield]

aku wrote:

I'm looking for the absolute fastest way
to count the nr of bits that are set to "1"
in a string. Presumably I then first need the
fastest way to do this in a byte.

I think this is it, but welcome any improvements:

i = 0;
if (g && 1) i++;
You mean &
if (g && 2) i++;
if (g && 3) i++;
You mean g & 4
if (g && 4) i++;
You mean g & 8
if (g && 5) i++;

You mean g & 16

etc

A lookup table would probably be faster, though.
--
Richard Heathfield : bi****@eton.pow ernet.co.uk
"Usenet is a strange place." - Dennis M Ritchie, 29 July 1999.
C FAQ: http://www.eskimo.com/~scs/C-faq/top.html
K&R answers, C books, etc: http://users.powernet.co.uk/eton

[Alex]

Stephen Mayes <st*****@themay eshouse.us> wrote:

"Alex" <al*******@hotm ail.com> wrote in message
news:br******** ****@ID-190529.news.uni-berlin.de...

Now, try again, preferably by using CHAR_BIT and a loop.
When you get it right, feel free to optimize.

I would appreciate any critique of this code. It might not be fast, but is
it correct and will it work?
Looks pretty good to me. My comments below are minor.
#include <stdio.h>
#include <stdlib.h> // is this required for below code ??
No, you don't need it. Also, unless you have a C99 compiler,
the double-slash comments are syntax errors. When posting in
news groups, they may wrap incorrectly, hence try not to use
them here.
#include <limits.h> int count_ones( char c )
Why not have this function take an unsigned char in the
first place, then lose the 't'.
{
int i = 0;
int count = 0;
unsigned char t = c;
unsigned char bit = 0x01; // what if CHAR_BIT != 8 ??
It's not a problem here. You are effectively doing

unsigned char bit = 1;

for( i = 0; i < CHAR_BIT; i++, bit <<= 1 ) {
if ( t & bit )
count++;
As far as I can see, there is nothing wrong with this. However,
stylistically I'd prefer to see the bit shift done inside the
body of the loop.
}
return count;
} int main( void )
{
char c = (char)0; // whatever
You don't need the cast. 0 is also not the most exciting
number to test this with :-)
int count = 0; count = count_ones( c );
printf( "There are %d bits set to 1.\n", count );
return 0;
}

Alex

[Andrey Tarasevich]

aku wrote:

I'm looking for the absolute fastest way
to count the nr of bits that are set to "1"
in a string. Presumably I then first need the
fastest way to do this in a byte.

I think this is it, but welcome any improvements:

i = 0;
if (g && 1) i++;
if (g && 2) i++;
if (g && 3) i++;
if (g && 4) i++;
if (g && 5) i++;
if (g && 6) i++;
if (g && 7) i++;
if (g && 8) i++;

For a 8-bit byte the look-up table is one way to go. Another solution
would be to do something along the lines of the following

g = (g & 0x55u) + ((g >> 1) & 0x55u);
g = (g & 0x33u) + ((g >> 2) & 0x33u);
g = (g & 0x0fu) + ((g >> 4) & 0x0fu);
/* now g contains the total number of 1 bits in the
original value of g */

--
Best regards,
Andrey Tarasevich

[Sidney Cadot]

aku wrote:

I'm looking for the absolute fastest way
to count the nr of bits that are set to "1"
in a string. Presumably I then first need the
fastest way to do this in a byte.

I think this is it, but welcome any improvements:

i = 0;
if (g && 1) i++;
if (g && 2) i++;
if (g && 3) i++;
if (g && 4) i++;
if (g && 5) i++;
if (g && 6) i++;
if (g && 7) i++;
if (g && 8) i++;

That's not correct, as others pointed out. What you're writing here is
equivalent to:

i = g ? 8 : 0;

(...how I yearn for a triple '&&&' operator...)

The lookup table, as suggested by others, is as fast as it gets on many
architectures, though it will bloat your code a bit if written
explicitly (and might lead to unexpected performance loss under some
circumstances if the LUT thrashes the processor cache, although this
should be rare).

One obvious solution that wasn't mentioned so far:

unsigned bits(const unsigned n)
{
return n ? n&1 + bits(n>>1) : 0;
}

Something like this would be useable for initializing your lookup table
at program start.
Best regards,

Sidney

[Jack Klein]

On Fri, 19 Dec 2003 13:57:35 -0800, Bertrand Mollinier Toublet
<be************ *************** **@enst-bretagne.fr> wrote in
comp.lang.c:

aku wrote:

I'm looking for the absolute fastest way
to count the nr of bits that are set to "1"
in a string. Presumably I then first need the
fastest way to do this in a byte.

I think this is it, but welcome any improvements:

i = 0;
if (g && 1) i++;
if (g && 2) i++;
if (g && 3) i++;
if (g && 4) i++;
if (g && 5) i++;
if (g && 6) i++;
if (g && 7) i++;
if (g && 8) i++;

Besides Ben's accurate remark that your code will not do what you
expect, table lookup is generally considered the "absolute fastest way"
to do something. What you gain in speed, though, you lose in data size,
which is a classical tradeof. At the scale of a byte, this is still a
manageable table:

You mean at the scale of a byte in the implementations you are
familiar with. On some platforms the table would need to have 65,536
entries. On some platforms the table would need to have 16,777,216
entries. On some platforms the table would need to have 4,294,967,296
entries. I don't know of any platform off-hand where an even larger
table would be needed, but I wouldn't be too surprised if there were
some.

--
Jack Klein
Home: http://JK-Technology.Com
FAQs for
comp.lang.c http://www.eskimo.com/~scs/C-faq/top.html
comp.lang.c++ http://www.parashift.com/c++-faq-lite/
alt.comp.lang.l earn.c-c++ ftp://snurse-l.org/pub/acllc-c++/faq