Почему полезно подсчитывать количество бит?

Question

Я видел множество вопросов о подсчете количества установленных бит на входе insert type of, но почему это полезно?

Для тех, кто ищет алгоритмы подсчета битов, посмотрите здесь:

1. Подсчет общих битов в последовательности длинных без знака
2. Самый быстрый способ подсчета количества битовых переходов в беззнаковых целых числах
3. Как посчитать количество установленных бит в 32-разрядном целом числе?

Answer 1

Вы можете рассматривать строку битов как set, где 1 представляет членство в наборе для соответствующего элемента. Следовательно, счетчик битов дает population count набора.

Практические применения включают сжатие, криптографию и коды с исправлением ошибок. Смотрите, например wikipedia.org / wiki / Hamming_weight и wikipedia.org / wiki / Hamming_distance .

Answer 2

Некоторым людям нравится использовать растровые изображения, чтобы указать наличие / отсутствие «материала».

Существует простое средство взлома для выделения младшего значащего 1 бита в слове, преобразования его в поле единиц в битах под ним, а затем вы можете найти номер бита, посчитав 1-бит.

countbits((x XOR (x-1)))-1;

Смотри, как работает.

Let x =     00101100
Then x-1 =  00101011
x XOR x-1 = 00000111

У которого установлены 3 бита, поэтому бит 2 был наименее значимым 1-битом в исходном слове

Answer 3

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

Answer 4

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

Я не могу вспомнить ни разу, когда бы хотел сделать это за последние десять лет или около того, поэтому я подозреваю, что это скорее упражнение по программированию, чем практическая необходимость.