Efficient method for checking bits

Discussion in 'C++' started by joe, Apr 19, 2008.

  1. joe

    joe Guest

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

    }
    }
     
    joe, Apr 19, 2008
    #1
    1. Advertisements

  2. #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";

    }
     
    Erik Wikström, Apr 19, 2008
    #2
    1. Advertisements

  3. joe

    James Kanze Guest

    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.)
     
    James Kanze, Apr 20, 2008
    #3
  4. joe

    joe Guest

    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
     
    joe, Apr 20, 2008
    #4
  5. joe

    James Kanze Guest

    [...]
    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?
     
    James Kanze, Apr 20, 2008
    #5
  6. joe

    joe Guest

    And platform. I wouldn't really worry about it; the difference
    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, Apr 20, 2008
    #6
  7. joe

    joe Guest

    You are correct. The original code was !(input & 1), which is
    equivalent to the altered (~input & 1).
     
    joe, Apr 21, 2008
    #7
  8. joe

    joe Guest

    I find it rather unusual. Could you please post the assembly code you are
    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
     
    joe, Apr 21, 2008
    #8
  9. joe

    James Kanze Guest

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

    [...]
    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, Apr 21, 2008
    #9
  10. joe

    James Kanze Guest

    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.
    OK. That's a different situation to the one where I used it.
    (I had 256 bits, with typically only one or two set.)
     
    James Kanze, Apr 21, 2008
    #10
    1. Advertisements

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 (here). After that, you can post your question and our members will help you out.