2

对于给定first长度的位向量bitnum（<32），我需要遍历所有相同长度的字典顺序连续位向量。

例如，如果first是 011001（二进制）并且bitnum是 6，那么所有连续的都是：011011、011101、011111、111001、111011、111101、111111。另外，我也需要迭代 011001。

我的意思是字典顺序：

  • 如果 in 的第 i 位first是 '1'，那么 的第 i 位next必须是 '1'
  • 如果第 i 位first是 '0'，那么第 i 位next可以是 '0' 或 '1'

生成此类位向量的最快方法是什么？

现在我使用这个未优化的代码，它通过生成所有可能的位向量来工作，并检查每个向量是否遵循first字典中给定的方式。

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) );
}

我认为，如果代码只生成连续的位向量，它会更快。

First向量是具有该位长度的任何可能的向量。

生成向量的顺序可以不同。

如果你想对这个函数或你的版本进行基准测试，有一个小的基准测试器，只需添加一个循环.. 函数代码：

#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);
}

例如，对于 bitnum=16，此代码在我的 PC 上运行 6 秒。我需要使用具有更高位数的此功能，最多 31。

请帮我优化loop_over_all_lex_succ。

4

2 回答 2

2

我将建议一种看起来比原始问题中的更简单且可能更有效的蛮力方法：

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

在我的 2.67 GHz Core i7 MacBook Pro 上，问题中的代码在 2.1 秒内运行，而上述代码在 0.04 秒内运行，加速大约 50 倍。

于 2011-03-09T11:19:52.207 回答
2 
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) );
}

在这里我们进行增量，但我们first在每一步都重置所有 1 位。使用这样的代码，我们将只增加0最初的位。

于 2011-03-09T12:45:30.383 回答