Я изучаю битовые манипуляции и наткнулся на следующий код. Я пытаюсь понять, что он делает:
long func_c(unsigned long x) {
long val = 0;
// sums of bits in x (done in parallel for each byte segment)
for (int i = 0; i < 8; i++) {
val += (x & 0x0101010101010101L);
x >>= 1;
}
// adds the top 32 bits to the lowest 32 but why?
val += (val >> 32);
// adds the top 16 bits to the lowest 16 but why?
val += (val >> 16);
// adds the top 8 bits to the lowest 8 but why?
val += (val >> 8);
// gets the lowest byte
return val & 0xff;
}
Чего пытается достичь серия правых сдвигов?
Первое и самое важное: код неверен. Три строки в конце функции должны быть такими:
val += (val >> 32);
val += (val >> 16);
val += (val >> 8);
Ваши комментарии были правильными, но код — нет. С указанным выше изменением функция работает корректно.
Цикл for
создает в val
набор из 8 байтов, каждый из которых содержит количество битов «1» в соответствующем байте x
.
Помните, мы пытаемся получить количество битов «1» в исходном x
, и пока все, что у нас есть, это байт 0 из val
, содержащий количество битов «1» в байте 0 числа x, байт 1 значения val равен количество битов «1» в байте 1 числа x и т. д. Итак, мы хотим сложить 8 байтов val
.
Код получает дополнительный параллелизм за счет добавления верхних 4 байтов val
к нижним 4 байтам val
. Помните, что максимальное значение каждого байта равно 8, поэтому, когда вы складываете эти два 32-битных значения вместе, каждый байт добавляется к соответствующему другому байту без переполнения. Таким образом, 32-битный результат теперь содержит частичные суммы байтов оригинала val
.
Затем добейтесь большего параллелизма, разделив 32-битный результат на два 16-битных значения и сложив их вместе. И снова соответствующие байты складываются без переполнения.
Окончательное сложение двух половин 16-битного числа дает общее количество бит «1» в оригинале x
.
printf
твой друг.
Я думаю, что в исходном вопросе комментарии немного неверны. val >>= (val >> 32)
не добавляет верхние и нижние 32 бита, а val += (val >> 32)
добавляет.
Пожалуйста, посмотрите вывод этого примера кода:
#include <stdio.h>
int main()
{
unsigned long x = 0xffffffffffffffff;
long val = 0;
// sums of bits in x (done in parallel for each byte segment)
for (int i = 0; i < 8; i++) {
val += (x & 0x0101010101010101L);
x >>= 1;
printf("Val 1: 0x%lx / 0x%lx\r\n", val, x);
}
printf("Val 2: 0x%lx\r\n", (val >> 32));
printf("Val 3: 0x%lx\r\n", val >> 0x8080808);
// adds the top 32 bits to the lowest 32 but why?
val >>= (val >> 32);
printf("Val 4: 0x%lx\r\n", val);
// adds the top 16 bits to the lowest 16 but why?
val >>= (val >> 16);
printf("Val 5: 0x%lx\r\n", val);
// adds the top 8 bits to the lowest 8 but why?
val >>= (val >> 8);
printf("Val 6: 0x%lx\r\n", val);
// gets the lowest byte
long LastVal = val & 0xff;
printf("LastVal: %ld", LastVal);
return 0;
}
main.c: In function ‘main’:
main.c:27:36: warning: right shift count >= width of type [-Wshift-count-overflow]
27 | printf("Val 3: 0x%lx\r\n", val >> 0x8080808);
| ^~
Val 1: 0x101010101010101 / 0x7fffffffffffffff
Val 1: 0x202020202020202 / 0x3fffffffffffffff
Val 1: 0x303030303030303 / 0x1fffffffffffffff
Val 1: 0x404040404040404 / 0xfffffffffffffff
Val 1: 0x505050505050505 / 0x7ffffffffffffff
Val 1: 0x606060606060606 / 0x3ffffffffffffff
Val 1: 0x707070707070707 / 0x1ffffffffffffff
Val 1: 0x808080808080808 / 0xffffffffffffff
Val 2: 0x8080808
Val 3: 0x8080808080808
Val 4: 0x8080808080808
Val 5: 0x80808080808
Val 6: 0x808080808
LastVal: 8
Я считаю, что первая часть того, что сказал выше Стив Форд, верна, но вторая часть, касающаяся битовых сдвигов, ошибочна. Битовый сдвиг достигает максимума на 64 бита, ширина long. Следовательно, максимальное количество битовых сдвигов будет содержаться в двух нижних полубайтах, или в данном случае 0x08. Результирующее число представляет собой исходный бит числа, сдвинутый на 0x08 бит на каждой итерации.
Да, я заметил ошибку после нажатия кнопки «Отправить». Ответ теперь исправлен. Мне нравится, что вы сохранили ошибку и показали последствия. Но я не уверен, что ОП понял, почему были сделаны дополнения.
Предложите вам приложить больше усилий, чтобы ВЫДЕЛИТЬ, что код, показанный здесь, известен как ошибочный и неправильный. Одно дело объяснить, где и что такое ошибка. Попытка объяснить результаты выполнения ошибочного кода - это извращение...
Я извращенец. Если бы я мог проголосовать против моего ответа на мусорный мусор, я бы обязательно это сделал. Кроме того, я неправильно написал имя пользователя Стрива. Я оставлю этот ответ как есть, как предупреждение будущим поколениям не лажать так, как я лажаю.
Чтобы убедиться, что я не неправильно понял, вы знаете, что вы можете редактировать или удалять. Вы намеренно оставляете этот ответ с ошибкой. Но не делайте это очень ясно (например, используя форматирование, это редкий случай, когда немного шумное форматирование вызвало бы мои аплодисменты). И вы не перефразируете так, чтобы ваш (интересный и ценный) подход к обучению с помощью ошибок был очевиден с самого начала? Я за Fe2O3.
Да, я ценю отзывы каждого. Я понимаю, что могу редактировать свой ответ. Я просто чувствую, что исходный вопрос с его ошибками представляет собой более интересный вопрос, поэтому я оставил его нетронутым. Я уважаю мнения всех присутствующих здесь по поводу SO, потому что я многому у вас учусь. Я предпочитаю оставить свой ошибочный ответ своему потомству.
спасибо- да, извините:
>>=
должно было быть+=
.