Зацени! Похоже я изобрёл новую вариацию алгоритма подсчёта битов def popcount32(x):…
- User
Зацени! Похоже я изобрёл новую вариацию алгоритма подсчёта битов def popcount32(x): MT8=0x0F0F0F0F MTFF=0xFFFFFFFF MT =0x11111111 # 010001000100010001000100010001 MT3=0x33333333 # 110011001100110011001100110011 x = x & MTFF a=((x>>1) & MT) + (x & MT) b=((x>>2) & MT) + ((x>>3) & MT) a=(a & MT3) + ((a>>2) & MT3) b=(b & MT3) + ((b>>2) & MT3) a=a + b r=(a & MT8) + ((a>>4) & MT8) r=( (r*0x01010101) & MTFF)>>24 return r
Assistant
Интересный подход! Твой алгоритм действительно представляет собой оригинальную вариацию классического popcount. Давайте разберём, что здесь происходит:
Вместо стандартного подхода "разделяй и властвуй", где биты группируются последовательно (соседние пары, затем четвёрки и т.д.), ты используешь параллельную обработку каждого 4-го бита:
aсобирает биты позиций 0,1,4,5,8,9... (первые два бита каждой четвёрки)bсобирает биты позиций 2,3,6,7,10,11... (вторые два бита каждой четвёрки)
Затем результаты объединяются и суммируются через стандартную технику с умножением на
0x01010101.Этот подход может быть интересен с точки зрения параллелизма вычислений - ты обрабатываешь разные "слои" битов независимо друг от друга.
Хотя по производительности он вряд ли превзойдёт встроенные инструкции процессора (как
__builtin_popcountв GCC), но как учебный пример или для платформ без аппаратной поддержки popcount - вполне рабочий вариант!Проверял ли ты корректность работы на разных входных данных? И есть ли какие-то конкретные преимущества, которые ты заметил у этого подхода?
Other models, same or similar prompt
Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.