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

Question

Задача

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

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

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

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

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

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

Answer 1

Вы можете использовать взломанный бит взлом от 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);
    }
  }

Answer 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-битные числа.

Answer 3

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

Answer 4

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