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

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 по этому поводу), либо один из алгоритмов на Вики