16+
Воскресенье
17 февраля
Вход |Карта сайта | |Upload |codebook | PARTS

 О смысле всего сущего 0xFF

 Средства и методы разработки

 Мобильная и беспроводная связь

 Блошиный рынок Объявления

caxapa

Микроконтроллеры ARM 

AVR PIC MSP PLD,FPGA,DSP 

Кибернетика Технологии 

Схемы, платы, компоненты 

Средства и методы разработки

 
   Новая тема Правила Регистрация Поиск »» Архив
Вернуться в конференциюТопик полностью
fk0  (12.02.2019 12:52, ссылка) , в ответ на Сколько тактов потребуется RISC процессору, чтобы узнать кол-во отличных от нуля разрядов в 32-битном регистре? автор: Хаос
В общем случае проблема описана в "Алгоритмических трюках для программистов" Г. Уоррена. По ссылке (другой источник, но есть в онлайне) много деталей, практически же код выглядит так: 
    v = v - ((v >> 1) & 0x55555555);
    v = (v & 0x33333333) + ((v >> 2) & 0x33333333);
    return ((v + (v >> 4) & 0xF0F0F0F) * 0x1010101) >> 24;
Что микрософт компилирует такое (godbolt.org/z/hC84ov -- во что gcc не знаю, сломался):
        lsrs        r3,r0,#1
        bic         r3,r3,#0xAAAAAAAA
        subs        r1,r0,r3
        lsrs        r3,r1,#2
        bic         r2,r3,#0xCCCCCCCC
        bic         r3,r1,#0xCCCCCCCC
        add         r3,r3,r2
        add         r3,r3,r3,lsr #4
        bic         r2,r3,#0xF0F0F0F0
        mvn         r3,#0xFEFEFEFE
        mul         r3,r2,r3
        lsrs        r0,r3,#0x18
Что составляет 12 команд. Что сильно меньше, чем 100500. Такие вещи вообще обычно реализованы в функциях libgcc и написаны руками на ассемблере для конкретных архитектур, но в данном случае на C есть типовая для всех архитектур реализация: code.woboq.org/gcc/libgcc/libgcc2.c.html#841 (табличный способ используется только для всяких AVR'ов и RL78, не 32-битных машин). Кому сильно надо быстро пишут руками и под конкретную архитектуру, только эти кому сильно надо обычно сильны только в изучении отдельных ассемблерных команд отдельного процессора и тыкания ими всех налево и направо, и даже не понимают, что в общем объёме кода посчитать биты, даже если это алгоритм им. АОНа, обычно далеко не самое важное. Ссылка на Hackers Delight (www.hackersdelight.org/) по-русски "Алгоритмические трюки".
[ZX]
 [x][x][x][x][x][x] [x][x][x][x][x][x][x][x]

Тема выделяется по переводу строки или автоматом

 

Имя


Регистрация позволит вам редактировать и перемещать ваши сообщения и прикреплять к ним файлы.
 
Символы: á é ó ú ý « »
Главная | Карта сайта | О проекте | Проекты | Файлообменник | Регистрация | Вебмастер | RSS
Лето 7527 от сотворения мира. При использовании материалов сайта ссылка на caxapу обязательна.
MMI © MMXIX