plc4good.org.ua

Подсчет единичных битов в DWORD без циклов и условных переходов.



binary



При программировании PLC, необходимость в подсчете единичных битов возникает довольно часто, например: определение колличества нарушений.
В ситуации, когда возникает такая задача, первое что приходит на ум - организовать цикл с побитным перебором области и инкрементом суммы по условию наличия в бите единицы.
Оказывается это не единственный вариант...
Алгоритм взят из книги Генри Уоррен, мл. "Алгоритмические трюки для программистов" издание 2004 года.

Ниже приведен листинг программы на SCL подсчета единичных битов в двойном слове (DWORD):

 
FUNCTION FC999 : VOID
VAR_INPUT   IN: DWORD; END_VAR
VAR_OUTPUT OUT: INT; END_VAR
VAR_TEMP   x: DWORD;   END_VAR
 
x:=IN;
 
x:=DINT_TO_DWORD(DWORD_TO_DINT(x AND DW#16#55555555) + DWORD_TO_DINT((SHR(IN:=x,N:= 1) AND DW#16#55555555)));
x:=DINT_TO_DWORD(DWORD_TO_DINT(x AND DW#16#33333333) + DWORD_TO_DINT((SHR(IN:=x,N:= 2) AND DW#16#33333333)));
x:=DINT_TO_DWORD(DWORD_TO_DINT(x AND DW#16#0F0F0F0F) + DWORD_TO_DINT((SHR(IN:=x,N:= 4) AND DW#16#0F0F0F0F)));
x:=DINT_TO_DWORD(DWORD_TO_DINT(x AND DW#16#00FF00FF) + DWORD_TO_DINT((SHR(IN:=x,N:= 8) AND DW#16#00FF00FF)));
x:=DINT_TO_DWORD(DWORD_TO_DINT(x AND DW#16#0000FFFF) + DWORD_TO_DINT((SHR(IN:=x,N:=16) AND DW#16#0000FFFF)));
 
OUT:=DWORD_TO_INT(x);
END_FUNCTION

Каким образом это работает - понять невозможно :).

Более обычный вариант, показан в листинге ниже:

FUNCTION FC998 : VOID
VAR_INPUT   IN: DWORD; END_VAR
VAR_OUTPUT OUT: INT; END_VAR
VAR_TEMP   x: DWORD; sum: INT; i: INT; END_VAR
 
x:=IN;
sum:=0;
 
    FOR i:= 0 TO 31 BY 1 DO
 
        IF (x AND ROR(IN:=DW#16#1,N:=i)) <> 0
        THEN
            sum:=sum+1;
        END_IF;
    END_FOR;
OUT:=sum;
END_FUNCTION

Сравнивая их получим:

Параметр 1ый вариант 2ой вариант
Размер в рабочей памяти 274 байта 158 байт
Время выполнения (симулятор) 100тыс. вызовов. 35 мс. 152 мс.

Еще один вариант, предложенный в комментариях scl (размер 134 байта):

FUNCTION FC2 : VOID

VAR_INPUT
IN: DWORD;
END_VAR

VAR_OUTPUT
OUT: INT;
END_VAR
VAR_TEMP
s,i: INT;
END_VAR

s:=0;

FOR i:= 0 TO 31 DO
s:=s+DWORD_TO_INT(ROR(IN:=IN,N:=i) AND dw#16#1);
END_FOR;

OUT:=s;

END_FUNCTION

Назад