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]

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.

 

[Bertrand Mollinier Toublet]

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

 

[Alex]

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]

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]

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.

 

[Alex]

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]

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 */

 

[Sidney Cadot]

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]

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.learn.c-c++ ftp://snurse-l.org/pub/acllc-c++/faq

 

[Richard Heathfield]

Stephen Mayes wrote:

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

No, I don't see any need for it. By the way, unless you have a C99 compiler,
the above line contains a syntax error (BCPL comments were not introduced
into C until C99 arrived).

#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 ??

This is fine (apart from the "comment" again), but unsigned char bit = 1;
works just as well.

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

I find this unnecessarily complicated (although it should work okay). The
following loop is simpler, and thus easier to maintain:

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

Keep things simple.

}

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

No need for the cast. char c = 0; is perfectly legal code and does exactly
what you want.


Yes, as far as I can see, the code should work fine.

 

[Robert Stankowic]

aku wrote:

[....]

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.

What about

#include <stdlib.h>
#include <stdio.h>

int main(void)
{
int tbl[] = {0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4};
int count = 0;
/*"faked" example for CHAR_BIT == 32
(int is 32 bit in my implementation)*/
unsigned int to_test = 0x22098157;
printf("%d", to_test);

/*would be implementation defined for signed negative*/
for(; to_test; to_test >>= 4)
{
count += tbl[to_test &0x0f];
}
printf(" has %d bits set\n", count);
return EXIT_SUCCESS;
}

cheers
Robert

 

[Paul Hsieh]

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 */

Oooooo! Someone who actually knows something. I take it you were
*NOT* part of the C standard language committee. In any event you are
missing the finisher:

/* For 32 bits */
g *= 0x001010101;
return (g >> 24) & 0x3f;

 

[pete]

Sidney Cadot wrote:

One obvious solution that wasn't mentioned so far:

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

unsigned bit_count(unsigned n)
{
unsigned count;

for (count = 0; n; n &= n - 1) {
++count;
}
return count;
}

 

[Jarno A Wuolijoki]

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

I'm not a fan of excessive parenthesizing either, but I would still add
a couple of them there..

 

[Sidney Cadot]

unsigned bit_count(unsigned n)
{
unsigned count;

for (count = 0; n; n &= n - 1) {
++count;
}
return count;
}

This doesn't work. If you want to get rid of the recursion, this will do:

unsigned bit_count(unsigned n)
{
unsigned count;

for (count = 0; n; n>>=1) {
count+=n&1;
}
return count;
}

Best regards,

Sidney

 

[pete]

This doesn't work.

You're wrong.

If you want to get rid of the recursion, this will do:

unsigned bit_count(unsigned n)
{
unsigned count;

for (count = 0; n; n>>=1) {
count+=n&1;
}
return count;
}

Try harder.

/* BEGIN new.c */

#include <stdio.h>

#define LIMIT 256

unsigned bit_count(unsigned n)
{
unsigned count;

for (count = 0; n; n &= n - 1) {
++count;
}
return count;
}

unsigned bit_count2(unsigned n)
{
unsigned count;

for (count = 0; n; n>>=1) {
count+=n&1;
}
return count;
}

int main(void)
{
unsigned number;

for (number = 0; LIMIT != number; ++number) {
if (bit_count(number) != bit_count2(number)) {
break;
}
}
if (number == LIMIT) {
puts("Try harder.");
}
return 0;
}

/* END new.c */

 

[nrk]

This doesn't work. If you want to get rid of the recursion, this will do:

Wrong! It definitely works. This is the well-known "sparse-ones" log2
algorithm (the sparse-zeroes simply negates the input and counts the 0's
instead). Its running time is proportional to the number of set bits in
the input. Credited originally to DMR, I think. I've been told by a
knowledgeable ex-colleague that on machines with an FPU, frexp is faster
than any bit counting methods to obtain log2. Don't know if that's true or
not.

Also, I find no hint of recursion in the above code.

-nrk.

 

[Sidney Cadot]

You're wrong.

You're right. /my/ implementation was wrong because of some lacking
parentheses. Sorry.

Your solution is quite a clever thing; took me a couple of seconds to
see how it succeeds at knocking out a single bit with n even.

Try harder.

How's that? I don't see anything wrong with it.

if (number == LIMIT) {
puts("Try harder.");
}

I think you meant: number != LIMIT.

Best regards, Sidney

 

[Sidney Cadot]

Wrong! It definitely works. This is the well-known "sparse-ones" log2
algorithm (the sparse-zeroes simply negates the input and counts the 0's
instead). Its running time is proportional to the number of set bits in
the input. Credited originally to DMR, I think.

I botched it.... It's a clever little algorithm, this.

I've been told by a
knowledgeable ex-colleague that on machines with an FPU, frexp is faster
than any bit counting methods to obtain log2. Don't know if that's true or
not.

Also, I find no hint of recursion in the above code.

I thought Pete was trying to get rid of the recursion in my algorithm.

Best regards, Sidney