Русская Википедия:Алгоритм Гончарова
Алгоритм Гончарова — способ, позволяющий подсчитать количество рядов в битовой последовательности, где под словом «ряд» подразумевается непрерывная подпоследовательность одинаковых битов. Ряд длиной k бит состоит из k абсолютно идентичных битов, начинается и заканчивается с бита, содержащего противоположное значение.
Алгоритм
- <math> n = pop(x ~\oplus~ (x >> 1)) + 1 </math>
где:
- x — входное значение
- n — количество рядов
- pop — функция, подсчитывающая количество единичных битов
Реализация
// Подсчитывает количество рядов в первом элементе.
// Параметр prevHi возвращает состояние старшего бита в целях последующего объединения рядов, идущих через границу между элементами.
template <class T>
static unsigned int getNumberOfRowsFirst(T x, int &prevHi)
{
prevHi = 1 - (x & 1);
return getNumberOfRowsNext(x, prevHi);
}
// Подсчитывает количество рядов в следующем элементе.
// Параметр prevHi используется для объединения рядов, идущих через границу между элементами.
template <class T>
static unsigned int getNumberOfRowsNext(T x, int &prevHi)
{
unsigned int uiRes = pop(static_cast<T>(x ^ ((x << 1) | prevHi)));
prevHi = x >> ((sizeof(T) * 8) - 1);
return uiRes;
}
|
Тестирование
Для тестирования использовался неттоп на базе материнской платы N3160ND3V с процессором Intel(R) Celeron(R) CPU N3160 @ 1.60GHz.
ОС: Ubuntu 20.04.4 LTS (Focal Fossa)
Тестирование скорости выполнения было проведено для версий алгоритма с использованием поисковых таблиц и без них, для элементов размером от 8 до 128 бит..
Использовался блок данных размером 1 мегабайт. Скорость выполнения усреднялась на протяжении 100 эпох.
Выяснилось, что с таблицами и без них скорость выполнения получается практически одинаковая. Отклонения варьировались от запуска к запуску в пределах ±1%.
На указанном оборудовании алгоритм быстрее всего работает с элементами размером 64 бита (uint64_t):
>>>> Testing for elements of size 64 bits <<<<
...
Test without tables:
number of bit runs: 2097152
avg execution time: 1.49 uS
Test with tables:
number of bit runs: 2097152
avg execution time: 1.49 uSПримечания
Литература
Ссылки
- Репозиторий на github.com
- Шаблон:Нп3 → Hamming weight
- Шаблон:Нп3 → Bit Twiddling Hacks
- Статистические тесты NIST
