Как считать активные биты меньше, чем O(n)

Question

У меня есть бит длины n, сказать 0100010010 Как это все? 1не читает все 0(быстрее чем в O(n))?

Answer 1

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

Это эффективная программная функция подсчета населения от Delta 5-2 от Hacker's для 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;
}

Answer 2

Если вы не обладаете какими-либо другими знаниями или не наращиваете этот набор битов постепенно, сублинейное время, очевидно, невозможно.

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

Answer 3

На машинах с инструкцией popcnt() это наиболее эффективный способ. В других случаях для этого используются различные приемы, и наиболее эффективный способ может зависеть от вашей конкретной машины. Смотрите, например, https://graphics.stanford.edu/~seander/bithacks.html и другие разделы рядом с ним.