Как обработать очень длинную последовательность битов?

Question

Пусть у нас будет некоторая последовательность A, например, {-1, 3, 2, 5}.Мы можем выбрать все его непустые подпоследовательности, используя итерации (двоичный инкремент некоторого итератора) 1 .. 2^|A|:

int i, A[] = {-1, 3, 2, 5};

for (i = 1; i < (1 << sizeof(A)); i++)
{
  int t = i, p = 0;

  while (t > 0)
  {
    if (t % 2 > 0)
      printf("%d\t", a[p]);

    t /= 2, p++;
  }

  printf("\n");
}

Но что мы должны делать, если A содержит, например, 5000000 элементов?Например, как обработать 5-миллиардное число?

Answer 1

Ну, есть неуравновешенный набор алгоритмов, которые выполняют такие задачи, которые называются «алгоритмы перечисления».В основном они касаются таких вопросов, как: 1. Что такое i-е непустое подмножество всех подмножеств?2. Что является непустым подмножеством, каков следующий элемент?или предыдущий 3. Для непустого подмножества, каков ранг этого подмножества?

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

Интересная книга, посвященная этим вопросам: Комбинаторные алгоритмы, Генерация, Перечисление, Поиск К. Россена.У меня также есть набор слайдов на эту тему, хотя я не знаю, как их прикрепить.Проверьте сайт Люсии Моуры, курс Комбинаторные алгоритмы.

(если вам нужны детали любого из этих алгоритмов выше, дайте мне знать, пожалуйста)

Answer 2

Возможно, вы захотите начать оптимизировать его с помощью CUDA или SSE, как это делает bitmagic .

вы также можете проверить, являются ли байты полностью нулевыми, и пропустить их полностью, а используя BSR, BSF и LCZ, вы можете пропустить нулевые биты и просто распечатать нули для количества пропущенных бит.