В чем заключается сложность подсчета единиц в двоичной записи больших чисел?

Сложности подсчёта единиц в двоичной записи больших чисел могут заключаться в большом количестве операций сдвига и сравнений. 3 Например, при использовании некоторых методов, чтобы добраться до единицы в исходном числе, нужно сдвигать либо само число, либо единицу несколько раз и выполнять сравнение с единицей. 3

Также для больших чисел может быть неприменим табличный метод, который предполагает первоначальное заполнение массива количества единиц в числе для некоторого диапазона чисел, а затем подстановку значения из массива, зная число в заданном диапазоне. 4 Такой способ требует больше ёмкостных ресурсов на хранение массива количества единиц, а также временных ресурсов на заполнение исходного массива значений, но сам подсчёт количества единиц в числе осуществляется быстрее. 4

Для решения задачи подсчёта единиц в двоичном представлении числа можно использовать, например, метод Кёрнигана, основанный на свойстве, что операция n & (n-1) обнуляет в числе последнюю единицу. 4