Расчет веса Хэмминга в O (1)

Question

В двоичном представлении вес взлома - это количество 1. Я наткнулся на сети и нашел O (1) ответ на него:

v = v - ((v>>1) & 0x55555555); 
v = (v & 0x33333333) + ((v>>2) & 0x33333333); 
int count = ((v + (v>>4) & 0xF0F0F0F) * 0x1010101) >> 24; 

Однако я не совсем понимаю, алгоритм и не может найти его описание в любом месте. Может кто-нибудь, пожалуйста, объясните это немного, особенно последняя строка (что означает «черт» * 0x1010101, а затем >> 24 означает)?

Answer 1

Это часть стратегии разделения и покоя для подсчета бит, называемой функцией «совокупность». Научную трактовку этой стратегии можно найти в Reingold и Nievergelt, 1977.

Идея состоит в том, чтобы сначала суммировать биты попарно, затем по 4, затем по 8 и так далее. Например, если у вас есть биты 1011, тогда первая пара 10 станет 01, потому что есть один бит, а второй становится 10, потому что 10 = 2 в двоичном формате и есть два бита в 11. Существенным фактом является то, что:

population(x) = x - (x/2) - (x/4) - (x/8) - (x/16) - ... etc. 

Точный алгоритм у вас есть вариант того, что известно как алгоритм «HAKMEM» (см Beeler, Госпером и Schroppel, 1972). Этот алгоритм вычисляет 1 в 4-битных полях параллельно, то эти суммы преобразуются в 8-разрядные суммы. Последним шагом является операция по добавлению этих 4 байтов путем умножения на 0x01010101. Маска 0x0F0F0F0F получает 4-мульные суммы байтов, маскируя информацию без суммы. Например, предположим, что 8-мульное поле 10110110, тогда есть 5 бит, который равен 0101, таким образом, у нас будет 10110101. Только последние четыре бита являются значительными, поэтому мы маскировать первые четыре, а именно:

10110101 & 0x0F = 00000101 

Вы можете найти целую главу о мелочах подсчета битов в книге «Делайт Хакер» Генри Уоррен.