plc4good.org.ua/view_post.php?id=91
При программировании PLC, необходимость в подсчете единичных битов возникает довольно часто, например: определение количества нарушений.
В ситуации, когда возникает такая задача, первое что приходит на ум – организовать цикл с побитным перебором области и инкрементом суммы по условию наличия в бите единицы.
Оказывается это не единственный вариант…
Алгоритм взят из книги Генри Уоррен, мл. ‘Алгоритмические трюки для программистов’ издание 2004 года.
Ниже приведен листинг программы на SCL подсчета единичных битов в двойном слове (DWORD):
FUNCTION FC999 : VOID
VAR_INPUT IN: DWORD, END_VAR
VAR_OUTPUT OUT: INT, END_VAR
VAR_TEMP x: DWORD, END_VARx:=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_VARx:=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
Комментарии к материалу
Добавлен: 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?
Оцените статью!