Как этот код работает для подсчета количества 1-бит?
Я нашел следующий код для подсчета количества 1-bits в двоичном представлении для данного целого числа. Кто-нибудь может объяснить, как это работает? И как битовые маски выбираются для такой задачи? Благодарю.
int count_one(int x)
{
x = (x & (0x55555555)) + ((x >> 1) & (0x55555555));
x = (x & (0x33333333)) + ((x >> 2) & (0x33333333));
x = (x & (0x0f0f0f0f)) + ((x >> 4) & (0x0f0f0f0f));
x = (x & (0x00ff00ff)) + ((x >> 8) & (0x00ff00ff));
x = (x & (0x0000ffff)) + ((x >> 16) & (0x0000ffff));
return x;
}
Решение
Этот алгоритм использует x как источник вычислений и как память. Сначала подумайте, что такое битовые маски:
0x55 = 01010101
0x33 = 00110011
0x0f = 00001111
0xff = 11111111
Давайте рассмотрим 8-битный пример: a = 01101010
a & 0x55 = 01000000; (a >> 1) & 0x55 = 00010101
Если мы сложим эти два значения вместе, мы получим количество бит для каждой двухбитной пары. Этот результат не более 0x10, поскольку маска имеет только один бит, установленный для каждого добавления.
Теперь мы используем 0x33 маска, помните, что каждые 2 последовательных бита содержат результат первой операции. С помощью этой маски мы маскируем последовательные 4 бита и добавляем их. Этот результат не более 0x100, Это продолжается с другими масками, пока мы не получим результат в x,
Попробуйте на бумаге, через несколько шагов все станет ясно.
Другие решения
Это подход «разделяй и властвуй». Обратите внимание, что в первой строке будет указана сумма для последующих пар, затем сумма для последующих четверок, … и, наконец, количество битов.
Пример (16 бит, поэтому рассмотрите ваш код без последней строки)
1011001111000110
В первой линии мы берем & с четными и нечетными битами, сдвинутыми на единицу. Тогда мы добавим.
Для четных битов:
num: 10 11 00 11 11 00 01 10
mask: 01 01 01 01 01 01 01 01
res: 00 01 00 01 01 00 01 00
Для нечетных битов:
num>>1: 01 01 10 01 11 10 00 11
mask: 01 01 01 01 01 01 01 01
res: 01 01 00 01 01 00 00 01
Мы добавляем эти результаты и получаем суммы в последующих парах
01 10 00 10 10 00 01 01
Мы повторяем то же самое со следующими масками и соответствующими сменами
2nd: 0011 0011 0011 0011
3rd: 0000 1111 0000 1111
4th: 0000 0000 1111 1111
И мы получаем:
2nd: 0011 0010 0010 0010 // 3 set in the first four, 2 in other quadrupels
3rd: 0000 0101 0000 0100 // 5 bits set in the first eight, 4 in the rest
4th: 0000 0000 0000 1001 // 9 bits in total
Чтобы было проще это объяснить, позвольте мне предположить, что целое число имеет длину 4 бита, и каждый бит представлен как 1,2,3,4. Для того, чтобы получить количество 1-bitsВы можете сначала получить сумму 1 и 2 и сумму 3 и 4, а затем сложить эти суммы.
x & (0x5) исключит 1 и 3, и x & (0xa) устранят 2 и 4. x & (0x5) + (x & (0xa) >> 1) будет использовать 1 2 бита для хранения суммы 1 и 2 и использовать 3 4 бита для хранения суммы 3 и 4. x & (0x5) + (x & (0xa) >> 1) такой же как x & (0x5) + (x >> 1) & (0x5),
Теперь у нас есть суммы 1 2 и 3 4, все они хранятся в x, мы можем получить результат после их сложения. То же, что и выше, x & (0x3) получит сумму 3 4 и x & (0x12) получит сумму 1 2. x & (0x3) + (x & (0x12)) >> 2 получит окончательный результат. x & (0x3) + (x & (0x12)) >> 2 такой же как x & (0x3) + (x >> 2) & (0x3),
Таким образом, вы можете увидеть, что происходит внутри. В вашем случае в первой строке вы можете получить сумму 1 2 и 3 4 и 5 6 и продолжить. А во второй строке вы получаете сумму 1 2 3 4 и 5 6 7 8 и продолжаете. Делая это 5 раз, вы получите число всех 32 бит.
В первой строке целое число рассматривается как массив из 16 2-битных целых, результат выражения равен 0, если были установлены 0 битов в 2-битной паре, 1, если был установлен 1 бит в 2-битной паре (01 бин или 10 бинов) и 2, если установлены оба бита 2-битной пары. Это потому, что мы рассматриваем младшую из каждых двух битов xи младший из каждых двух битов x сдвинут вправо на единицу; добавляя их вместе. Мы знаем, что переносы вне 2-битных пар не произойдут, потому что наши слагаемые ограничены 0 или 1. Затем результат сохраняется в x,
x = (x & (0x55555555)) + ((x >> 1) & (0x55555555));
Следующая строка делает то же самое, на этот раз обрабатывая каждые 2 бита как отдельное целое число, сохраняя их сумму в каждых 4 битах, которые занимали два слагаемых. После этой операции целое число по существу становится массивом из 8 4-битных целых чисел. Перед операцией каждое слагаемое имеет значение 0, 1 или 2 (десятичное число), поскольку оно соответствует отсчетам из последней строки. Из-за этого мы знаем, что каждая сумма будет не больше 4. Поскольку каждое 4-битное int имеет максимальное значение 15 (десятичное число), мы знаем, что это также не будет переполнено. Как и выше, результат сохраняется в x,
x = (x & (0x33333333)) + ((x >> 2) & (0x33333333));
Мы делаем то же, что и выше, на этот раз суммируя каждую пару из 4 битов в каждый набор из 8 битов.
x = (x & (0x0f0f0f0f)) + ((x >> 4) & (0x0f0f0f0f));
Затем мы суммируем пару из 8 бит в каждую пару из 16 бит (верхняя и нижняя половина x).
x = (x & (0x00ff00ff)) + ((x >> 8) & (0x00ff00ff));
Суммируем верхнюю и нижнюю половину xи у нас осталось 32-битное значение, равное количеству битов, установленных в значении x,
x = (x & (0x0000ffff)) + ((x >> 16) & (0x0000ffff));
Ключевым моментом здесь является то, что каждый шаг выполняет попарный подсчет битов до тех пор, пока у нас не останется общее количество бит в 32-битном целом числе.
detector