Efficient method for checking bits

[joe]

Has anyone have any ideas for a possibly more efficient approach to
conditionally executing code based on bits being set (to zero)?

example attempt: If the particular bit is set to 0, do something (in
this case increment a particular output)

void foo(int input,int* output)
{
if( !(input & 1) )
{
output[0] ++;
}
if( !(input & 2) )
{
output[1]++;
}
if( !(input & 4) )
{
output[2]++;
}
..etc..

}
}

 

[Erik Wikström]

Has anyone have any ideas for a possibly more efficient approach to
conditionally executing code based on bits being set (to zero)?

example attempt: If the particular bit is set to 0, do something (in
this case increment a particular output)

void foo(int input,int* output)
{
if( !(input & 1) )
{
output[0] ++;
}
if( !(input & 2) )
{
output[1]++;
}
if( !(input & 4) )
{
output[2]++;
}
..etc..

}
}

#include <iostream>

void foo(unsigned char input, int* output)
{
for (int i = 0; i < sizeof(unsigned char) * 8; ++i)
if (input & (1 << i))
++output;
}


int main()
{
int out[sizeof(unsigned char) * 8];
for (int i = 0; i < sizeof(unsigned char) * 8; ++i)
out = 0;

foo(0xAA, out);

for (int i = 0; i < sizeof(unsigned char) * 8; ++i)
std::cout << out << "\n";

}

 

[James Kanze]

Has anyone have any ideas for a possibly more efficient
approach to conditionally executing code based on bits being
set (to zero)?

example attempt: If the particular bit is set to 0, do
something (in this case increment a particular output)

void foo(int input,int* output)
{
if( !(input & 1) )
{
output[0] ++;
}
if( !(input & 2) )
{
output[1]++;
}
if( !(input & 4) )
{
output[2]++;
}
..etc..
}

In this particular case:

void
foo( unsigned input, int* output )
{
while ( input != 0 ) {
if ( (input & 1) != 0 ) {
++ (*output) ;
}
++ output ;
input >>= 1 ;
}
}

(It's a bit tricker with a signed int, since the sign may be
propagated by the right shift. In general, I would avoid signed
types when dealing with bits.)

 

[joe]

Has anyone have any ideas for a possibly more efficient
approach to conditionally executing code based on bits being
set (to zero)?
example attempt: If the particular bit is set to 0, do
something (in this case increment a particular output)
void foo(int input,int* output)
{
if( !(input & 1) )
{
output[0] ++;
}
if( !(input & 2) )
{
output[1]++;
}
if( !(input & 4) )
{
output[2]++;
}
..etc..
}

In this particular case:

void
foo( unsigned input, int* output )
{
while ( input != 0 ) {
if ( (input & 1) != 0 ) {
++ (*output) ;
}
++ output ;
input >>= 1 ;
}
}

(It's a bit tricker with a signed int, since the sign may be
propagated by the right shift. In general, I would avoid signed
types when dealing with bits.)

Thanks. Playing around with it more, I found that the statement:
if( ~input & 1) was faster than if( (input & 1) != 0) on my
particular compiler (gnu). Looking at the assembly output I can see
why; although some other compilers I've tried optimize both to the
same machine code. Don't know if that's a missed gnu optimization, or
gnu is just being more pedantic about violating some standards rule.

It also proved faster to create a templated compile-time loop instead
of an explicit loop with a loop conditional.
Thanks

 

[James Kanze]

On Apr 20, 4:42 am, James Kanze <[email protected]> wrote:

[...]

Thanks. Playing around with it more, I found that the statement:
if( ~input & 1) was faster than if( (input & 1) != 0) on my
particular compiler (gnu).

And platform. I wouldn't really worry about it; the difference
is unlikely to be measurable.

Looking at the assembly output I can see why; although some
other compilers I've tried optimize both to the same machine
code. Don't know if that's a missed gnu optimization, or gnu
is just being more pedantic about violating some standards
rule.

If the results are the same, then the optimization is legal.

It also proved faster to create a templated compile-time loop
instead of an explicit loop with a loop conditional.

How can you create a templated compile-time loop when the number
of times you go through the loop isn't known until runtime?

 

[joe]

And platform. I wouldn't really worry about it; the difference

is unlikely to be measurable.


If the results are the same, then the optimization is legal.


How can you create a templated compile-time loop when the number
of times you go through the loop isn't known until runtime?

The difference was pretty measurable. About a 20% speed-up for the
total application. As for the loop, the number of iterations is
known at compile time (there are only so many bits in an unsigned int
to loop through). In this particular application, it is equally as
likely for any bit to be set, so there is no advantage to trying to
exit early.

Thanks for the comments

 

[joe]

Except that it is not the same thing. More like the opposite of the original
statement.

You are correct. The original code was !(input & 1), which is
equivalent to the altered (~input & 1).

 

[joe]

I find it rather unusual. Could you please post the assembly code you are

referring to?

The following program:
#include <iostream>
int main(int arg, char **argv)
{
int input = atoi(argv[1]);
int a = 0;
if(~input & 1) a++;
if(~input & 2) a++;
if(~input & 4) a++;
if(~input & 8) a++;
if(~input & 16) a++;
std::cout<<a<<std::endl;
}

using "g++ 3.4.6 -O3 -S" on linux generates code that seems to have 3
less machine instructions than if I replace the lines with if(!(input
& ...)) a++;

It runs slower, and other compilers produce equally sized machine
output and have no speed improvement.

Thanks,
Joe

 

[James Kanze]

@telia.com> wrote in comp.lang.c++:

[...]

The line above could fail miserably on platforms where there
are more than 8 bits in an unsigned char, and yes they do
exist. And have C++ compilers.

Yes and no. Just because more bits are available doesn't mean
that you have to use them.

[...]

There's a perfectly good macro named CHAR_BIT in
<climits>/<limits.h>, that eliminates this completely needless
unportability.

It depends on what you are doing. If you're formatting bit
fields in an IP header block, for example, you're better off
using 8 (which will be the same on all machines, and is what the
IP standard requires) than CHAR_BIT.

 

[James Kanze]

The difference was pretty measurable. About a 20% speed-up
for the total application. As for the loop, the number of
iterations is known at compile time (there are only so many
bits in an unsigned int to loop through).

The number of iterations isn't known, and will frequently be
less than the number of bits in an unsigned int. If most of the
bits are set, most of the time, then using a template to unwind
the loop will improve performance. If the upper bits are often
not set, then it will slow things down.

In this particular application, it is equally as likely for
any bit to be set, so there is no advantage to trying to exit
early.

OK. That's a different situation to the one where I used it.
(I had 256 bits, with typically only one or two set.)