-2
У меня есть битсет длиной n. скажем 0100010010 Как ta claculate все его 1 не читает все 0 (быстрее, чем в O (n))?Как подсчитать активные биты меньше, чем O (n)
A
ответ
2
Нет, для подсчета нет сублинейного метода. Но существует существенная разница в постоянном коэффициенте между методами подсчета O (n). Битовый набор должен быть реализован внутренне, используя размер родного слова хост-архитектуры и, в идеале, использовать собственную инструкцию подсчета бит, если она доступна.
Это эффективная функция подсчета численности программного обеспечения от Hacker's Delight 5-2 для 32-разрядного номера. Вы можете расширить технику до более крупных целочисленных типов, а для числового типа с произвольной точностью вы можете применить этот метод к компонентам числа и добавить их вместе.
int count(unsigned i) {
i = i - ((i >> 1) & 0x55555555);
i = (i & 0x33333333) + ((i >> 2) & 0x33333333);
i = (i + (i >> 4)) & 0x0f0f0f0f;
i = i + (i >> 8);
i = i + (i >> 16);
return i & 0x3f;
}
+0
и сложность - это ... O (n). –
+0
@ KarolyHorvath в этом конкретном случае сложность O (1), потому что N здесь постоянна (32 или 64) –
+0
Вопрос явно говорит, что битсет имеет размер 'n' (который не является константой). – amit
1
В машинах, у которых есть команда popcnt(), является наиболее эффективным способом. В других случаях для этого используются различные трюки, и наиболее эффективный способ может зависеть от вашей конкретной машины. См. https://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetKernighan и других местах рядом.
1
Если вы не владеете каким-либо другим знанием или не наращиваете этот биттет постепенно, сублинейное время, очевидно, невозможно.
Сам вход имеет размер O(n), и вам нужно будет прочитать каждый его бит, чтобы получить правильный ответ, в результате чего нижняя граница Omega(n).
Какой язык? Или вам просто нужен общий алгоритм? – nurdyguy
создайте предварительно рассчитанную таблицу для всех возможных вариантов, тогда у вас может быть либо avg O (1), если это хэш-карта, либо O (logN) для двоичного поиска –
Я думаю, что ваш вопрос уже решен [здесь] (http: /stackoverflow.com/questions/3815165/how-to-implement-bitcount-using-only-bitwise-operators) – gr1ph00n