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

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

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


c++ algorithm bitset
person gibraltar    schedule 03.10.2011    source источник
comment
Это уже O(n) из-за амортизации.   -  person flight    schedule 03.10.2011
comment
@quasiverse, не могли бы вы уточнить вышеизложенное?   -  person gibraltar    schedule 03.10.2011
comment
@quasiverse: если я понял, о чем вы говорите, битсет изначально не имеет амортизации, поскольку это контейнер фиксированной длины.   -  person Matteo Italia    schedule 03.10.2011
comment
может быть полезно знать, почему вы хотите сделать это с битовым набором, а не с целым   -  person jk.    schedule 03.10.2011
comment
@джк. Как вы можете легко сделать вывод, я пытаюсь решить проблему суммы подмножества. Чтобы быстро вычислить сумму подмножества, я реализовал функцию для скалярного произведения между набором битов и вектором‹int›. Также std::bitset предоставляет мне широкий набор полезных функций, которые в противном случае мне пришлось бы писать самому. Но я открыт для предложений, если есть какие-либо другие структуры данных, которые можно использовать вместо std::bitset   -  person gibraltar    schedule 03.10.2011

Ответы (2)


arrow_upward
1
arrow_downward

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

Оригинал статьи Горовица и Сахни:
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

person Piotr Kukielka    schedule 03.10.2011

arrow_upward
1
arrow_downward

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

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

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

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

person Mike Seymour    schedule 03.10.2011
comment
+1 это было в основном то, о чем я думал, за исключением сохранения отдельного беззнакового длинного для поддержания счетчика - person jk.; 03.10.2011