В двоичном представлении вес взлома - это число 1. Я наткнулся на веб-сайт и нашел для него ответ O (1):
v = v - ((v>>1) & 0x55555555);
v = (v & 0x33333333) + ((v>>2) & 0x33333333);
int count = ((v + (v>>4) & 0xF0F0F0F) * 0x1010101) >> 24;
Однако я не совсем понимаю алгоритм и не могу найти его описание нигде. Может кто-нибудь, пожалуйста, объясните это немного, особенно последняя строка (что означает "черт" * 0x1010101, а затем → 24 означает)?
Это часть стратегии разделения и покоя для подсчета бит, называемой функцией "населенности". Научное отношение к этой стратегии можно найти в Рейнгольде и Нивергельте, 1977 г.
Идея состоит в том, чтобы сначала суммировать биты попарно, затем по 4, затем по 8 и т.д. Например, если у вас есть биты 1011, тогда первая пара 10 становится 01, потому что есть один бит, а второй становится 10, потому что 10 = 2 в двоичном формате и есть два бита в 11, Существенным фактом здесь является то, что:
population(x) = x - (x/2) - (x/4) - (x/8) - (x/16) - ... etc.
Точный алгоритм, который у вас есть, - это вариант так называемого алгоритма "HAKMEM" (см. Beeler, Gosper and Schroppel, 1972). Этот алгоритм вычисляет 1 в 4-битных полях параллельно, затем эти суммы преобразуются в 8-разрядные суммы. Последним шагом является операция добавления этих 4 байтов путем умножения на 0x01010101. Маска 0x0F0F0F0F получает 4-мульные суммы байтов, маскируя информацию без суммы. Например, предположим, что 8-мульное поле 10110110, тогда есть 5 бит, равный 0101, поэтому мы будем иметь 10110101. Только последние четыре бита значительны, поэтому мы маскируем первые четыре, то есть:
10110101 & 0x0F = 00000101
Вы можете найти целую главу о мелочах подсчета бит в книге Генри Уоррена "Хакерский восторг".