Какие существуют способы эффективного подсчета единиц в бинарной записи больших чисел?

Один из эффективных способов подсчёта единиц в двоичной записи числа —  использование бинарной операции «И». ru.stackoverflow.com

Алгоритм: пока число (его нужно интерпретировать как беззнаковое число, чтобы подсчитать все единицы) не равно нулю, выполнить операцию «n &= n - 1» и увеличить счётчик единиц на единицу. ru.stackoverflow.com

Принцип: например, если в числе есть одна единица (0b00100000), то после вычитания 1 (0b00011111) нужно применить бинарную операцию «И» (0b00100000 & 0b00011111). ru.stackoverflow.com В результате число станет равным 0 (0b00000000), следовательно, оно содержало только одну единицу, так как операция была проделана только один раз. ru.stackoverflow.com

Также можно использовать алгоритмическое разделение строки: разделить двоичную строку на «1» и подсчитать количество единиц (count = размер вектора, содержащего разбиение, - 1). stackoverflow.com

Пользователь

Время добавления