Создание нескольких номеров с определенным количеством битов

Проблема

Мне нужно создать 32 битовых номера (подписанный или неподписанный не имеет значения, самый старший бит никогда не будет установлен в любом случае), и каждый номер должен иметь заданное количество битов.

Наивное решение

Самое простое решение - это, конечно, начать с нуля. В цикле число теперь увеличивается на единицу, подсчитывается количество битов, если счетчик имеет желаемое значение, номер сохраняется в списке, если цикл не повторяется. Цикл остановлен, если найдено достаточно чисел. Конечно, это работает отлично, но это ужасно медленно, как только количество желаемых бит становится очень высоким.

Лучшее решение

Простейшее число, имеющее (скажем) 5 Битов, заданное число, в котором установлены первые 5 бит. Этот номер можно легко создать. Внутри цикла устанавливается первый бит, а число сдвигается влево на единицу. Этот цикл работает 5 раз, и я нашел первое число с 5 битами. Следующие пару чисел легко создать. Теперь мы притворим, что число должно быть 6 бит в ширину, а верхнее - не установлено. Теперь мы начинаем смещать первый нулевой бит вправо, поэтому получаем 101111, 110111, 111011, 111101, 111110. Мы могли бы повторить это, добавив еще один фронт и повторить этот процесс. 0111110, 1011110, 1101110 и т.д. Однако таким образом числа будут расти намного быстрее, чем необходимо, поскольку, используя этот простой подход, мы оставляем числа, подобные 1010111.

Итак, есть ли лучший способ создать все возможные перестановки, общий подход, который можно использовать, независимо от того, сколько бит будет иметь следующий номер и независимо от того, сколько наборов бит нужно установить?

Ответ 1

Вы можете использовать бит-twiddling взломать с hackersdelight.org.

В своей книге у него есть код для получения следующего более высокого номера с одинаковым количеством однобитовых наборов.

Если вы используете это как примитив, чтобы увеличить свой номер, все, что вам нужно сделать, это найти начальную точку. Получение первого номера с N битными наборами очень просто. Это просто 2 ^ (N-1) -1.

Вы будете очень быстро перебирать все возможные числа.

  unsigned next_set_of_n_elements(unsigned x) 
  {
     unsigned smallest, ripple, new_smallest, ones;

     if (x == 0) return 0;
     smallest     = (x & -x);
     ripple       = x + smallest;
     new_smallest = (ripple & -ripple);
     ones         = ((new_smallest/smallest) >> 1) - 1;
     return ripple | ones;
  }

  // test code (shown for two-bit digits)

  void test (void)
  {
    int bits = 2;
    int a = pow(2,bits) - 1;
    int i;

    for (i=0; i<100; i++)
    {
       printf ("next number is %d\n", a);
       a = next_set_of_n_elements(a);
    }
  }

Ответ 2

Попробуйте приблизиться к проблеме с противоположной стороны - то, что вы пытаетесь сделать, эквивалентно "найти n чисел в диапазоне 0-31".

Предположим, вы пытаетесь найти 4 числа. Вы начинаете с [0,1,2,3], а затем каждый раз увеличиваете последнее число (получая [0,1,2,4], [0,1,2,5]...), пока не достигнете предела [0,1,2,31]. Затем увеличьте предпоследнее число и установите последнее число на один выше: [0,1,3,4]. Вернитесь к увеличению последнего числа: [0,1,3,5], [0,1,3,6]... и т.д. Как только вы достигнете конца этого, вы вернетесь к [0,1,4, 5] - в итоге вы достигнете [0,1,30,31], в этот момент вам нужно вернуться назад на следующий шаг: [0,2,3,4] и снова выйти. Продолжайте, пока вы, наконец, не закончите с [28,29,30,31].

Учитывая набор чисел, очевидно, легко преобразовать их в 32-битные номера.

Ответ 3

Вы хотите сгенерировать комбинации, см. эту статью в Википедии.

Ответ 4

Вам либо нужны факторальные перестановки (Google), либо один из алгоритмов Wiki