N-бит x, содержащий L 1s

Question

N-бит x, содержащий L 1s

Есть ли быстрые алгоритмы, которые могут хранить все различные N-битные числа, которые содержат L битов в 1 с? С N и L параметрами. Это для взлома криптосистемы в классе, и я заметил, что с помощью двух временных атак я могу узнать длину в битах (N) и количество в 1 бит (L).

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

Любые советы на всех будет принята с благодарностью.

Я использую C ++.

4

algorithm bit-manipulation c++combinatorics

Решение

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

Черт … templatetypedef получил ответ, который, вероятно, лучше моего. Я написал рекурсивный алгоритм для их генерации. Вероятно, не так, как вы хотите, но похоже, что это работает (Отказ от ответственности: минимальное тестирование!).

Я оставлю это здесь для потомков, хотя это может быть не лучшим способом сделать это. В отличие от другого ответа, этот даст вам вектор, содержащий все возможные комбинации. Очевидно, что это не идеальный подход, если у вас много миллионов / миллиардов комбинаций! Тем не менее, я хотел получить удовольствие от написания алгоритма для этого. Итак, миссия выполнена.

#include <bitset>
#include <vector>
using namespace std;

const int N = 4;

void addValues(int to_add, int start_pos, bitset<N> const& working, vector<bitset<N>>& values)
{
// Take all of our possible spots
for (int i = start_pos; i < N && i <= N - to_add; ++i) {
auto working_copy(working);
working_copy[i] = 1;

// We have more bits to set...
if (to_add > 1) {
addValues(to_add - 1, i + 1, working_copy, values);
}
// We've set all the bits, so this is a working combination
else {
values.push_back(working_copy);
}
}
}

int main(int argc, char* argv)
{
int L = 2;

vector<bitset<N>> values;
bitset<N> working;
addValues(L, 0, working, values);

return EXIT_SUCCESS;
}

2

Источник

Accepted Answer

Бит Тиддлинг Хаки На странице показано, как перечислить все двоичные числа с ровно n битами, установленными с использованием O (1) работы на генерируемое число. Их решение перепечатано здесь:

Предположим, у нас есть шаблон из N битов, установленный в 1 в целом числе, и мы хотим
следующая перестановка из N 1 бит в лексикографическом смысле. За
Например, если N равно 3, а битовый шаблон равен 00010011, следующие шаблоны
будет 00010101, 00010110, 00011001,00011010, 00011100, 00100011,
и так далее. Ниже приведен быстрый способ вычисления следующего
перестановка.
unsigned int v; // current permutation of bits
unsigned int w; // next permutation of bits

unsigned int t = v | (v - 1); // t gets v's least significant 0 bits set to 1

// Next set to 1 the most significant bit to change,
// set to 0 the least significant ones, and add the necessary 1 bits.
w = (t + 1) | (((~t & -~t) - 1) >> (__builtin_ctz(v) + 1));
__builtin_ctz(v) Встроенный компилятор GNU C для процессоров x86 возвращает число конечных нулей. Если вы используете компиляторы Microsoft для
х86, присуще _BitScanForward, Они оба излучают BSF
инструкция, но эквиваленты могут быть доступны для других архитектур.
Если нет, то рассмотрите возможность использования одного из методов подсчета
последовательные нулевые биты, упомянутые ранее. Вот еще одна версия, которая
имеет тенденцию быть медленнее из-за своего оператора деления, но это не
требуют подсчета завершающих нулей.
unsigned int t = (v | (v - 1)) + 1;
w = t | ((((t & -t) / (v & -v)) >> 1) - 1);

Начиная с числа всех 0, за исключением последних L битов, которые являются всеми 1, вы должны быть в состоянии использовать это, чтобы перечислить все числа, которые вы хотите.

Надеюсь это поможет!

4