Реализация двоичного счетчика с использованием std :: bitset

Question

Я хочу реализовать двоичный счетчик в C ++, используя std::bitset. Если бы я явно разработал функцию сложения для bitset, то сложность алгоритма возросла бы до O (n ^ 2). Есть ли способ сделать это O (n)?

Также есть ли хорошие описания решения проблемы суммы подмножеств Горовица и Сахни? За исключением Википедии, я не смог найти хорошего источника, описывающего их алгоритм.

Answer 1

Если набор битов настолько мал, что все биты могут поместиться в unsigned long, то вы можете использовать его функции преобразования для выполнения целочисленной арифметики, например,

bitset = std::bitset(bitset.to_ulong() + 1);

В C ++ 11 также есть функция to_ullong(), дающая unsigned long long, которая может быть больше, чем unsigned long.

Если ваши битовые наборы слишком велики для этого, вам может быть лучше реализовать свой собственный, основанный на массиве или векторе целых чисел, к которому ваш счетчик может получить доступ. Ваш алгоритм все равно будет O (n ² ), но вы можете уменьшить количество операций, необходимых для каждого добавления, по сравнению с обработкой одного бита за раз.

Answer 2

На ваш второй вопрос: «Есть ли хорошие описания решения проблемы подмножества Горовица и Сахни?», Я нашел несколько статей:

Оригинальная бумага от Горовица и Сахни:
http://www.cise.ufl.edu/~sahni/papers/computingPartitions.pdf

Обсуждение Stackoverflow об улучшениях алгоритма Горовица и Сахни:
Генерирует все суммы подмножеств в диапазоне быстрее, чем O ((k + N) * 2 ^ (N / 2))?

Исходный код:
http://www.diku.dk/hjemmesider/ansatte/pisinger/subsum.c