Может кто-нибудь объяснить, как работает этот код bitCount?

Это код, который моя ТА помогает мне получить, но потом я совершенно забыл, как это сработало, потому что, похоже, я не могу получить правильный ответ, а оценка интервью - завтра. Если кто-нибудь может помочь, пожалуйста, сделайте. Спасибо

* bitCount - returns count of number of 1's in word
*   Examples: bitCount(5) = 2, bitCount(7) = 3
*   Legal ops: ! ~ & ^ | + << >>
*   Max ops: 40
*   Rating: 4
*/
int bitCount(int x) {
    int m4 = 0x1 | (0x1<<8) | (0x1<<16) | (0x1<<24);
    int m1 = 0xFF; 
    int s4 = (x&m4) + ((x>>1)&m4) + ((x>>2)&m4) + ((x>>3)&m4) + ((x>>4)&m4) + ((x>>5)&m4) + ((x>>6)&m4) + ((x>>7)&m4);
    int s1 = (s4&m1) + ((s4>>8)&m1) + ((s4>>16)&m1) + ((s4>>24)&m1);
    return s1;
}
Источник

2 ответа

Решение

Часто проще увидеть, что происходит в битовой операции, когда вы преобразуете ее в битовое представление:

Предполагая, что int 32-битный, тогда следующие m4 & m1 в их битовом представлении:

0000 0001 0000 0001 0000 0001 0000 0001 //m4, masking across the 4 bytes
0000 0000 0000 0000 0000 0000 1111 1111 //m1, masking only 1 byte, the Least Significant Byte (LSB)

Я полагаю, что m обозначает маску, в то время как 4 и 1 означают 4 байта и 1 байт соответственно.

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

Во-первых, обратите внимание на сдвиг вправо и маскирование с помощью m4:

pqrs tuvw pqrs tuvw pqrs tuvw pqrs tuvw // x
0000 0001 0000 0001 0000 0001 0000 0001 //m4
---------------------------------------- &
0000 000w 0000 000w 0000 000w 0000 000w //x&m4

pqrs tuvw pqrs tuvw pqrs tuvw pqrs tuvw // x
---------------------------------------- >> 1
0pqr stuv wpqr stuv wpqr stuv wpqr stuv // x >> 1
0000 0001 0000 0001 0000 0001 0000 0001 //m4
---------------------------------------- &
0000 000v 0000 000v 0000 000v 0000 000v //(x>>1)&m4
.
.
pqrs tuvw pqrs tuvw pqrs tuvw pqrs tuvw // x
---------------------------------------- >> 7
0000 000p qrst uvwp qrst uvwp qrst uvwp // x >> 7
0000 0001 0000 0001 0000 0001 0000 0001 //m4
---------------------------------------- &
0000 000p 0000 000p 0000 000p 0000 000p //(x>>7)&m4

И во-вторых, обратите внимание на добавление 8 элементов, полученных из приведенных выше результатов:

0000 000w 0000 000w 0000 000w 0000 000w //x&m4
0000 000v 0000 000v 0000 000v 0000 000v //(x>>1)&m4
.
.
0000 000p 0000 000p 0000 000p 0000 000p //(x>>7)&m4
---------------------------------------- +
//Resulting in s4

Таким образом, поскольку каждый от p до w может быть только 0 или 1, и у вас есть восемь таких элементов, следовательно, на 8-битный сегмент у вас есть:

p+q+r+s+t+u+v+w // each element is either 0 or 1

Отсюда ясно видно, что результат для добавления 8 элементов выше будет в диапазоне от 0 до 8.

То есть вы получите от 0000 0000 (0 в десятичном представлении - если все равно 0) до 0000 1000 (8 в десятичном представлении - если все равно 1) на 8-битный сегмент.

Следовательно, у вас будет s4 в следующем формате:

0000 abcd 0000 efgh 0000 ijkl 0000 mnop // s4

Где abcd, efgh, ijkl и mnop являются результатом добавления p к w на байт.

Теперь обратите внимание, что вы получаете сумму количества бит в х, распределенных по 4 байтам.

(сумма, я полагаю, это то, что s в переменных означает - сумма)

0000 abcd //byte 1, left most, MSB
0000 efgh //byte 2, second from left
0000 ijkl //byte 3, second from right
0000 mnop //byte 4, rightmost, LSB

Таким образом, вам нужно объединить результат в этих четырех байтах в s4, чтобы найти сумму в одном байте

(и я полагаю, это то, что означает s 1: сумма в одном байте)

Вы получаете s 1 по:

  1. Сдвиг s4 с 0, 8, 16, 24
  2. Маскируйте каждого из них с 0xFF
  3. И объединить (добавить) результаты.

Следовательно, выполняются следующие операции (на уровне битов):

0000 abcd 0000 efgh 0000 ijkl 0000 mnop // s4
0000 0000 0000 0000 0000 0000 1111 1111 //m1 
--------------------------------------- &
0000 0000 0000 0000 0000 0000 0000 mnop

0000 0000 0000 abcd 0000 efgh 0000 ijkl // s4 >> 8
0000 0000 0000 0000 0000 0000 1111 1111 //m1 
--------------------------------------- &
0000 0000 0000 0000 0000 0000 0000 ijkl

.
.

0000 0000 0000 0000 0000 0000 0000 abcd // s4 >> 24
0000 0000 0000 0000 0000 0000 1111 1111 //m1 
--------------------------------------- &
0000 0000 0000 0000 0000 0000 0000 abcd

Видно, что у вас просто есть следующие добавления из четырех элементов:

0000 0000 0000 0000 0000 0000 0000 mnop //0 to 8
0000 0000 0000 0000 0000 0000 0000 ijkl //0 to 8
0000 0000 0000 0000 0000 0000 0000 efgh //0 to 8
0000 0000 0000 0000 0000 0000 0000 abcd //0 to 8
--------------------------------------- +
//Final result, s1

У вас есть простое добавление четырех чисел, каждое из которых имеет значение от 0 до 8. Таким образом, это должно привести к значению от 0 до 32 (0 - это когда все равно 0, 32 - когда все равно 8), что является числом бит 1 в переменной х. И поэтому функция называется bitCount.

Вот как работает функция.

Последнее замечание: зная это, вы даже можете изменить m1 с 0x0F (вместо 0xFF), и результат останется прежним.

Источник

После этого заявления:

    int s4 = (x&m4) + ((x>>1)&m4) + ((x>>2)&m4) + ((x>>3)&m4) + ((x>>4)&m4) + ((x>>5)&m4) + ((x>>6)&m4) + ((x>>7)&m4);

Поскольку в S4 есть 4 байта, то в 1 байте будет число 1 в соответствующем байте x Итак, очевидно, что каждый байт s4 содержит число 1 в соответствующем байте x.

Тогда в выражении: int s1 = (s4&m1) + ((s4>>8)&m1) + ((s4>>16)&m1) + ((s4>>24)&m1);

Теперь 1 байт s4 будет иметь число 1 в соответствующем байте x, тогда сдвиг вправо от s4 до 8 бит даст число 2 в байте 2 x, так что для 4 байтов. Тогда добавление всех даст число 1 в х.

Источник
Другие вопросы по тегам