CODEWITHSUNDEEP
coptimizationbit-manipulationmicro-optimization
osgx
osgx

Reputation: 94385

Looping over all lexicographical successive numbers

For given bit vector first of length bitnum (<32) I need to iterate over all lexicographical successive bit vectors of same length.

For example, if first is 011001 (binary) and bitnum is 6, then all successive are: 011011, 011101, 011111, 111001, 111011, 111101, 111111. Also, I need to iterate over 011001 too.

What I mean lexicographical successive:

What is the fastest way of generating such bit vectors?

Now I use this unoptimized code, It works by generating all possible bit vectors and check every vector is it follow the given first in lexicographical way. 

uint32_t loop_over_all_lex_succ(int bitnum, uint32_t first) {
    uint32_t next = first;
    uint32_t tmp;
    do { 
      target_function(next);

      do {
        next++;
        tmp = (~first|next); // sets the 0 bit at offset iff `next` has a 0 bit and `first` has 1
        tmp = ~tmp; // invert tmp; now all invalid bits are marked with '1'
        tmp = tmp & ((1<<bitnum)-1); // mask the tmp with target bit number

      } while( (next < (1<<bitnum))  && tmp );

    } while ( next < (1<<bitnum) );
}

I think, that if code will generate only successive bit vectors, it will be faster.

First vectors are any possible vector with this bit length.

Ordering of generated vectors can be different.

If you want to benchmark this function or your versions of it, there is a small benchmarker, just add a loop.. function code:

#include <stdio.h>
#include <stdint.h>
uint32_t count =0;
void target_function(uint32_t a) { count++; }
/* loop_over_all_lex_succ() here */
int main() {
    uint32_t f;
    int bitnum=16;  // you can increase it up to 31
    for(f=0;f<(1<<bitnum);f++)
        loop_over_all_lex_succ(bitnum,f);
    printf("bits: %d,  count of pairs: %u\n",bitnum,count);
}

For example for bitnum=16 this code runs 6 sec on my PC. I need to use this function with higher bit count, up to 31.

Please, help me optimize loop_over_all_lex_succ.

Upvotes: 2

Views: 202

Answers (2)

Paul R
Paul R

Reputation: 213060

I'll suggest a brute force approach that seems simpler and possibly more efficient than the one in the original question:

uint32_t loop_over_all_lex_succ(int bitnum, uint32_t first) {
    const uint32_t last = 1 << bitnum;
    uint32_t value;

    for (value = first;
         value < last;
         value = (value + 1) | first)
    {
        target_function(value);
    }
    return value;
}

On my 2.67 GHz Core i7 MacBook Pro, the code in the question runs in 2.1 s, whereas the above code runs in 0.04 s, for a speed-up of around 50x.

Upvotes: 2

osgx
osgx

Reputation: 94385

uint32_t loop_over_all_lex_succ(int bitnum, uint32_t first) {
    uint32_t next = first;
    uint32_t tmp;
    do { 
      target_function(next);
      next = (next +1 ) |first;
    } while ( next < (1<<bitnum) );
}

Here we do an increment, but also we reset all 1 bits from first at every step. With such code we will increment only bits, which were 0 in first.

Upvotes: 2

Related Questions