Какую логику использовать побитовую операцию при генерации подпоследовательностей?

Question

Какую логику использовать побитовую операцию при генерации подпоследовательностей?

У меня есть массив, A = [1,2,3,4] (где n = 4). Я хочу генерировать подпоследовательности из этого массива.
Количество подпоследовательностей равно (2 ^ n -1)

Пробег от счетчика 0001 до 1111

for (int counter = 1; counter < 2^n; counter++)
{
for (int j = 0; j < n; j++)
{

Проверьте, установлен ли j-й бит в счетчике. Если установлено, то вывести j-й элемент из arr []

        if (counter & (1<<j))
cout << arr[j] << " ";
}
cout << endl;
}
}

кто-нибудь может мне объяснить? Как это работает «счетчик & (1<

0

arrays c++logic subsequence

Решение

Другие решения

Других решений пока нет …

Источник

Accepted Answer

Логика такова. Скажем, как вы положили в примере, у вас есть n = 4и, чтобы избежать путаницы, скажем, массив A = [5, 7, 8, 9], например. Затем вы хотите все возможные последовательности, содержащие некоторые элементы (по крайней мере, один) из исходного массива. Таким образом, вам нужна последовательность, содержащая только первое, последовательность, содержащая первое и второе, первое и третье и т. Д. Каждая напечатанная последовательность может содержать или не содержать каждый из элементов в массиве. Таким образом, вы можете увидеть это примерно так:

| 5 | 7 | 8 | 9 |    Sequence
-----------------    --------
| 1 | 0 | 0 | 0 | -> 5
| 1 | 1 | 0 | 0 | -> 5 7
| 1 | 0 | 1 | 0 | -> 5 8
...

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

В этом цикле:

for (int counter = 1; counter < 2^n; counter++)

Программа повторяется от 1 в 2^n - 1, то есть 15 в этом случае. Таким образом, ценности, которые вы получаете за counter являются:

Dec  Binary
---  ------
1    0001
2    0010
3    0011
4    0100
5    0101
6    0110
7    0111
8    1000
9    1001
10    1010
11    1011
12    1100
13    1101
14    1110
15    1111

Если вы внимательно посмотрите, вы увидите, что у нас есть все возможные последовательности из четырех элементов, состоящих из 0 а также 1 в двоичном (кроме 0000, которая была бы пустой последовательностью и нас не интересует). В этом цикле:

for (int j = 0; j < n; j++)

Программа просто проходит каждый бит counter, от 0 (самый правый) n - 1 и всякий раз, когда он находит 1 он выводит соответствующий элемент массива. Состояние:

if (counter & (1<<j))

Просто вычисляет число 1<<j который 1 плюс j количество нулей справа (так, например, для j = 0 это было бы 1 и для j = 2 это было бы 100), а затем побитовая и операция, поэтому он в основном «фильтрует» jтолько один бит (например, 1101 & 100 = 0100), а если результат не равен нулю, значит, был один, и так arr[j] должен быть напечатан.

Очевидно, проблема с функцией заключается в том, что она ограничена количеством битов, которые переменная counter может держать. Это зависит от его объявленного типа и вашей архитектуры / компилятора, но обычно это будет 32 или 64.

3