Битовые манипуляции, перестановка битов

Question

Я пытаюсь создать цикл, который проходит по всем разным целым числам, где ровно 10 из последних 40 битов установлены в верхние, а остальные - в низкие. Причина в том, что у меня есть карта с 40 различными значениями, и я хочу суммировать все различные способы умножения десяти из этих значений. (Это просто из любопытства, поэтому интерес представляет именно «битовый манипулятор», а не сумма как таковая.)

Если бы я делал это, например, 2 из 4 битов, было бы легко установить все вручную,

0011 = 3,
0101 = 5,
1001 = 9,
0110 = 6,
1010 = 10,
1100 = 12,

, но с 10 из 40 я не могу найти способ для их эффективного создания. Я попытался, начиная с 1023 (= 1111111111 в двоичном формате), найти хороший способ манипулировать этим, но безуспешно. Я пытался сделать это в C ++, но это действительно общий метод (если есть), который представляет интерес. Я немного погуглил, но с небольшим успехом, если у кого-то есть хорошая ссылка, это, конечно, тоже будет оценено. :)

Answer 1

Вы можете использовать любую стандартную реализацию алгоритма выбора / комбинации. В основном вы хотите выбрать 10 бит из 40, которые будут установлены на 1.

Тем не менее, 40 выберите 10 847 660 528 . И это число будет умножено на любое количество возможных «хвостовых» битов, которых нет в верхних 40. Предположительно, на хвостовые биты не распространяются никакие правила, поэтому, если есть k бит, это быть другим фактором 2 ^k .

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

Похожие вопросы

• Алгоритм возврата всех комбинаций k элементов из n

Answer 2

Существует очень неочевидный способ сделать это эффективно: метод Госпера для нахождения следующего более высокого целого числа с тем же числом 1 битов из HAKMEM элемент 175.

lowest_1_bit = prev_combo & -prev_combo;
tmp = prev_combo + lowest_1_bit;
new_combo = (((prev_combo ^ tmp) >> 2) / lowest_1_bit) | tmp;

• первая строка находит самый правый 1 бит;
• второй поворачивает самый правый цикл из 1 битов в 0, а 0 только слева от цикла в 1;
• третья строка заменяет 1 битов, которые были потеряны второй строкой, в нижней части слова.

Теперь (при условии, что вы используете 64-битный целочисленный тип) вы можете начать с 1023 и просто применять его повторно (пока результат не превысит 1<<40).

Answer 3

Немного сложнее, но сделано просто с помощью битовых манипуляций. Ваш пример:

#define WIDTH 4
#define BITS 2

void printbits(long pattern) {
  long bit;
  for (bit = 1L << WIDTH - 1; bit; bit >>= 1)
    putchar(pattern & bit ? 49 : 48);
  putchar('\n');
}

void movebits(pattern, bit) {
  long mask = 3L << bit;
  while (((pattern ^= mask) & mask) && (mask < 1L << WIDTH)) {
    mask <<= 1;
    printbits(pattern);
    if (bit)
      movebits(pattern, bit - 1);
  }
}

int main() {
  long pattern = (1L << BITS) - 1L, mask;
  printbits(pattern);
  movebits(pattern, BITS - 1);
}

Ваше реальное приложение:

#define WIDTH 40
#define BITS 10

и, как говорится в Polygenelubricants, будьте готовы немного подождать :) Конечно, вы замените printbits чем-то более полезным для вас ...

(отредактировано для недостаточного тестирования: / Черт, опечатки ...)

Answer 4

Вы можете просто использовать next_permutation. Вот образец для воспроизведения вашего случая 2 из 4 (порядок немного меняется):

#include <iostream>
#include <algorithm>
using namespace std;
int main () {
 int bits[] = {0,0,1,1};

 do {
  for (int i = 0; i < 4; ++i) cout << bits[i] << " ";
  cout << endl;
 } while ( next_permutation (bits,bits+4) );
 return 0;
}

Answer 5

Это проще, если переписать это как набор вложенных циклов, указывающих позиции битов:

0011 = 0 1
0101 = 0 2
1001 = 0 3
0110 = 1 2
1010 = 1 3
1100 = 2 3

То есть позиция P1 первого бита изменяется от 0 до 3-1, а позиция второго бита P2 повторяется от P1 + 1 до 3. Превращение этого в общую рекурсивную функцию остается в виде упражнение.