Версия для печати

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

Дата: 2010-10-12

Добавлено: komatic

Тема: SCL



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





Просмотров: 15905

Комментарии к материалу

Добавлен: piranius    Дата: 2010-10-14

тут дилема либо большая скорость исполнения при большом размере кода, либо меньший размер кода при большом времени исполнения. Несколько команд ассемблера обмена меж регистрами типа PUSH-POP гораздо быстрее по исполнению одной команды загрузки типа MOV :)

Добавлен: Serge_UA    Дата: 2011-01-14

1ый вариант - это алгоритм подсчета веса Хемминга. Подробнее он описан в Википедии в статье "Hamming weight"

Добавлен: Serge_UA    Дата: 2011-01-14

Если размер битового массива известен и он не слишком большой, то лучше использовать второй вариант; организовать его в STL и без использования цикла (т.е. написать операции детектирования бита и инкрементирования суммы N раз). ИМХО быстродействие будет с

Добавлен: Serge_UA    Дата: 2011-01-14

...опоставимо с первым вариантом, зато алгоритм прост и понятен. Эксплуатирующий персонал вам за это спасибо скажет.

Добавлен: scl    Дата: 2011-08-09

Вот еще один вариант (размер 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

Добавлен: scl    Дата: 2011-08-09

_TO_INT(ROR(IN:=IN,N:=i) AND dw#16#1);
END_FOR;
OUT:=s;
END_FUNCTION

Добавлен: komatic    Дата: 2011-08-09

добавил, этот вариант в материал.

Добавлен: Erema    Дата: 2011-10-14

Кусок из FB (c FC не проверял). Кстати, кто нибудь может проверить соотношения времени и размеров памяти

FUNCTION_BLOCK FB111
VAR_INPUT
IN: DWORD;
VIEW AT IN: ARRAY[0..31] OF BOOL;
END_VAR

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

Добавлен: Erema    Дата: 2011-10-14

_VAR
s:=0;
FOR i:= 0 TO 31 DO
IF VIEW[i] THEN s:=s+1; END_IF;
END_FOR;
OUT:=s;
END_FUNCTION_BLOCK

Добавлен: Serex    Дата: 2012-06-22

Я бы сделал по другому. Сколько это займет, не знаю.
FUNCTION "Block_1" : Void

VAR_INPUT
"DWORD" : DWord;
END_VAR

VAR_OUTPUT
"OUT" : Int;
END_VAR

VAR_TEMP
"t" : DIn

Добавлен: Serex    Дата: 2012-06-22

VAR_TEMP
"t" : DInt;
"s" : Int;
"a" : DInt;
END_VAR



BEGIN
#a:=16#80000000;
#t:= DWORD_TO_DINT(#DWORD);
#s:=0;
WHILE #a>0 DO
IF (#t/#a)>0 THEN
#t:=#t-#a;
#s:=#s

Добавлен: Serex    Дата: 2012-06-22

А нафиг!! Это ужасно вставлять здесь код!!!

Добавлен: komatic    Дата: 2012-06-28

лучше использовать форум, если чтото длинное.

Добавлен: komatic    Дата: 2012-06-29

теперь длинные комментарии тоже принимаются

Добавлен: SHKODRAN    Дата: 2014-04-12

Вы также можете узнать, какие бит именно?
Can you know also which bit exactly of dword?

Добавить комментарий

Ваше имя:

Текст комментария (4000 max):

Введите сумму с картинки: