Биты

← →
ArtemESC (2005-08-17 19:27) [0]

Доброго времени суток...
Какой самый быстрый алгоритм подсчета количества нулей
и единиц в структуре или, хотя-бы в байте можете предложить?
Например: 01110001 -> 1 ноль
потом 3 единицы
потом 3 нуля
1 единица
Алгоритм хотелось бы сделать максимально быстрым,
поскольку операция будет с большими участками памяти.
Заранее спасибо!!!

← →
Alexander Panov © (2005-08-17 19:32) [1]

Использовать массив с возможными комбинациями битов в байте.

← →
GLFox © (2005-08-17 19:38) [2]

Для подсчета количества единичных битов я пользуюсь такой функцией:
function Bin32GetFlagCount(uFlags: Cardinal): Cardinal; begin Result := uFlags - ((uFlags shr 1) and $55555555); Result := (Result and $33333333) + ((Result shr 2) and $33333333); Result := (Result + (Result shr 4)) and $0f0f0f0f; Result := Result + (Result shr 8); Result := Result + (Result shr 16); Result := Result and $0000003f; end;
А вообще, читай книгу "Hacker"s Delight" автора Henry S. Warren, Jr.

← →
KilkennyCat © (2005-08-17 19:42) [3]

[1] шустрее.

← →
GLFox © (2005-08-17 19:46) [4]

>KilkennyCat © (17.08.05 19:42) [3]

Однако! Для 32-битного значения делать массив с 2^32 комбинациями, думаю накладнее будет...

← →
KilkennyCat © (2005-08-17 19:47) [5]

> 32-битного

???

← →
Alexander Panov © (2005-08-17 20:03) [6]

GLFox © (17.08.05 19:38) [2]
GLFox © (17.08.05 19:46) [4]

Вопрос о байте.
Следовательно массив будет состоять из 256 значений.

← →
ArtemESC (2005-08-17 20:09) [7]

>>Alexander Panov
>>Вопрос о байте.
Байт - это только для примера, который я
хотел получить от вас...В действительности
структуры будут довольно-таки большие.
Вот в чем дело. Как ускорить этот процесс???
Извеняюсь за требовательность, но очень нужно...

← →
Alexander Panov © (2005-08-17 20:15) [8]

ArtemESC (17.08.05 20:09) [7]
Вопрос надо задавать как следует, так как из условий задачи следует ее решение. А в случае поиска оптимальных решений частное не верно для общего в большинстве случаев.

Что касается новых условий, то получение количества битов побайтно(при условии оптимального решения для байта), как мне кажется, даст наибольшую производительность.

> Байт - это только для примера

не только. Байт - это минимум. 32 бита проверятся четыре раза по байту.

> ArtemESC (17.08.05 19:27)

самый быстрый алгоритм - с использованием таблиц преобразования.

но при использовании оного выигрывая в производительности кода ты ОЩУТИМО проигрываешь в размере данных, требуемых для работы алгоритма.

А нельзя использовать TStringStream? Число единиц и нулей ведь в байтах заранее известно. Сохранить в TStringStream и перебрать все байты в полученной строке. Или это не быстрый способ?

>[11]
По-моему, этот способ быстрый, если не учитывать стыки между байтами. Для учёта стыков придётся запоминать сколько и чего в начале и в конце байта. Потом суммировать длины совпадающих концов соседних байт. Плюс контроль за числами $00 и $FF, которые являются соеденительными между другими байтами. Stream для этого подойдёт любой. При грамотной реализации этот метод может оказаться самым быстрым.

Биты Найти похожие ветки