ВходНаше всё Теги codebook PARTS Поиск Опросы Закон Четверг
1 октября
/903307
Топик полностью
fk0 (12.02.2019 12:52, просмотров: 28) в ответ на Сколько тактов потребуется RISC процессору, чтобы узнать кол-во отличных от нуля разрядов в 32-битном регистре? - автор: Хаос
В общем случае проблема описана в "Алгоритмических трюках для программистов" Г. Уоррена. По ссылке (другой источник, но есть в онлайне) много деталей, практически же код выглядит так: ссылка v = v - ((v >> 1) & 0x55555555); v = (v & 0x33333333) + ((v >> 2) & 0x33333333); return ((v + (v >> 4) & 0xF0F0F0F) * 0x1010101) >> 24; Что микрософт компилирует такое (https://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 есть типовая для всех архитектур реализация: https://code.woboq.org/gcc …gcc/libgcc2.c.html#841 (табличный способ используется только для всяких AVR'ов и RL78, не 32-битных машин). Кому сильно надо быстро пишут руками и под конкретную архитектуру, только эти кому сильно надо обычно сильны только в изучении отдельных ассемблерных команд отдельного процессора и тыкания ими всех налево и направо, и даже не понимают, что в общем объёме кода посчитать биты, даже если это алгоритм им. АОНа, обычно далеко не самое важное. Ссылка на Hackers Delight (https://www.hackersdelight.org/) по-русски "Алгоритмические трюки".
[ZX]
Ответить
Ответы