Перебирая все лексикографические последовательные числа

Question

Для данного битового вектора first длины bitnum (<32) мне нужно перебрать все лексикографические последовательные битовые векторы одинаковой длины.</p>

Например, если first равно 011001 (двоичный) и bitnum равно 6, то все последующие: 011011, 011101, 011111, 111001, 111011, 111101, 111111. Кроме того, мне нужно выполнить итерациюза 011001 тоже.

Что я имею в виду лексикографически последовательно:

• , если 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 этот код выполняется на моем ПК 6 секунд.Мне нужно использовать эту функцию с большим количеством битов, до 31.

Пожалуйста, помогите мне оптимизировать loop_over_all_lex_succ.

Answer 1

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

Здесь мы делаем приращение, но также мы сбрасываем все 1 бит с first на каждом шаге. С таким кодом мы будем увеличивать только те биты, которые были 0 вначале.

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

На моем Core i7 MacBook Pro с частотой 2,67 ГГц код в вопросе работаетчерез 2,1 с, в то время как приведенный выше код выполняется за 0,04 с для ускорения примерно в 50 раз.