Битовые манипуляции

Я изучаю битовые манипуляции и наткнулся на следующий код. Я пытаюсь понять, что он делает:

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;
}

Чего пытается достичь серия правых сдвигов?

спасибо- да, извините: >>= должно было быть +=.

testing09 27.07.2024 18:56
Стоит ли изучать PHP в 2023-2024 годах?
Стоит ли изучать PHP в 2023-2024 годах?
Привет всем, сегодня я хочу высказать свои соображения по поводу вопроса, который я уже много раз получал в своем сообществе: "Стоит ли изучать PHP в...
Поведение ключевого слова "this" в стрелочной функции в сравнении с нормальной функцией
Поведение ключевого слова "this" в стрелочной функции в сравнении с нормальной функцией
В JavaScript одним из самых запутанных понятий является поведение ключевого слова "this" в стрелочной и обычной функциях.
Приемы CSS-макетирования - floats и Flexbox
Приемы CSS-макетирования - floats и Flexbox
Здравствуйте, друзья-студенты! Готовы совершенствовать свои навыки веб-дизайна? Сегодня в нашем путешествии мы рассмотрим приемы CSS-верстки - в...
Тестирование функциональных ngrx-эффектов в Angular 16 с помощью Jest
В системе управления состояниями ngrx, совместимой с Angular 16, появились функциональные эффекты. Это здорово и делает код определенно легче для...
Концепция локализации и ее применение в приложениях React ⚡️
Концепция локализации и ее применение в приложениях React ⚡️
Локализация - это процесс адаптации приложения к различным языкам и культурным требованиям. Это позволяет пользователям получить опыт, соответствующий...
Пользовательский скаляр GraphQL
Пользовательский скаляр GraphQL
Листовые узлы системы типов GraphQL называются скалярами. Достигнув скалярного типа, невозможно спуститься дальше по иерархии типов. Скалярный тип...
0
1
79
2
Перейти к ответу Данный вопрос помечен как решенный

Ответы 2

Ответ принят как подходящий

Первое и самое важное: код неверен. Три строки в конце функции должны быть такими:

  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 бит на каждой итерации.

Да, я заметил ошибку после нажатия кнопки «Отправить». Ответ теперь исправлен. Мне нравится, что вы сохранили ошибку и показали последствия. Но я не уверен, что ОП понял, почему были сделаны дополнения.

Streve Ford 27.07.2024 19:19

Предложите вам приложить больше усилий, чтобы ВЫДЕЛИТЬ, что код, показанный здесь, известен как ошибочный и неправильный. Одно дело объяснить, где и что такое ошибка. Попытка объяснить результаты выполнения ошибочного кода - это извращение...

Fe2O3 28.07.2024 01:30

Я извращенец. Если бы я мог проголосовать против моего ответа на мусорный мусор, я бы обязательно это сделал. Кроме того, я неправильно написал имя пользователя Стрива. Я оставлю этот ответ как есть, как предупреждение будущим поколениям не лажать так, как я лажаю.

thomas.cloud 28.07.2024 05:27

Чтобы убедиться, что я не неправильно понял, вы знаете, что вы можете редактировать или удалять. Вы намеренно оставляете этот ответ с ошибкой. Но не делайте это очень ясно (например, используя форматирование, это редкий случай, когда немного шумное форматирование вызвало бы мои аплодисменты). И вы не перефразируете так, чтобы ваш (интересный и ценный) подход к обучению с помощью ошибок был очевиден с самого начала? Я за Fe2O3.

Yunnosch 28.07.2024 07:05

Да, я ценю отзывы каждого. Я понимаю, что могу редактировать свой ответ. Я просто чувствую, что исходный вопрос с его ошибками представляет собой более интересный вопрос, поэтому я оставил его нетронутым. Я уважаю мнения всех присутствующих здесь по поводу SO, потому что я многому у вас учусь. Я предпочитаю оставить свой ошибочный ответ своему потомству.

thomas.cloud 28.07.2024 17:21

Другие вопросы по теме