Подскажите алгоритм оптимального чтения LSB num бит.
Есть число 11110000 = F0. Необходимо прочитать справа налево num bit, начиная с first.
Например: first = 2, num = 5, читаем 00111 = 7.
Первое что приходит:
int v = 0;
for (int i = first; i < num + first; i++)
v = (v << 1) + (value & (1 << i)) ? 1 : 0;
Здравствуйте, Vladimir, Вы писали:
V>Подскажите алгоритм оптимального чтения LSB num бит. V>Есть число 11110000 = F0. Необходимо прочитать справа налево num bit, начиная с first. V>Например: first = 2, num = 5, читаем 00111 = 7. V>Первое что приходит:
V>int v = 0;
V>for (int i = first; i < num + first; i++)
V> v = (v << 1) + (value & (1 << i)) ? 1 : 0;
V>Меня смущает цикл for и оператор if. V>Спасибо.
а чем такой вариант не устраивает?
в каком-то эмуляторе, скорее всего PPSSPP, который эмулирует MIPS, видел шаблоны, которые автоматом конвертируют LSB в MSB, а там уж обычные сдвиги и маски можно применить.
Не предлагаю копаться в таком гигантском коде, чтобы найти эти шаблоны, просто это направление, в котором можно поискать. Не факт даже, что шаблонами быстрее будет
Здравствуйте, Vladimir, Вы писали:
V>Подскажите алгоритм оптимального чтения LSB num бит. V>Есть число 11110000 = F0. Необходимо прочитать справа налево num bit, начиная с first. V>Например: first = 2, num = 5, читаем 00111 = 7.
Не понятно, для чего, какие ограничения. Нужно просто без циклов? Так пойдет?
#include <cstdint>
int main()
{
uint32_t value = 0xf0;
const uint32_t first = 2;
const uint32_t num = 5;
// reverse bits
value = ((value >> 1) & 0x55555555) | ((value & 0x55555555) << 1);
value = ((value >> 2) & 0x33333333) | ((value & 0x33333333) << 2);
value = ((value >> 4) & 0x0F0F0F0F) | ((value & 0x0F0F0F0F) << 4);
value = ((value >> 8) & 0x00FF00FF) | ((value & 0x00FF00FF) << 8);
value = ( value >> 16 ) | ( value << 16);
// get bit field
value = (value << first) >> (32 - num);
return value;
}
Здравствуйте, wl., Вы писали: wl.>а чем такой вариант не устраивает?
Конечная цель — чтение кодов Хаффмана.
Хотелось найти максимально производительный код!
Здравствуйте, Vladimir, Вы писали:
V>Подскажите алгоритм оптимального чтения LSB num бит. V>Есть число 11110000 = F0. Необходимо прочитать справа налево num bit, начиная с first. V>Например: first = 2, num = 5, читаем 00111 = 7.
Компилятор какой? И платформа?
У ARM, например, есть команда rbit, которая разворачивает все биты в слове.
Ну а её аналог с логарифмической сложностью уже есть в соседнем комментарии.
А извлечь начиная с нужной позиции — сдвиги и маскирование — тривиально (и в случае того же ARM делается одной командой ubfx; для x86 надо или shr и and, или shl и shr).
Но непонятно, зачем вообще такой разворот нужен. Уточните на более высоком уровне.
Здравствуйте, Vladimir, Вы писали:
V>Подскажите алгоритм оптимального чтения LSB num бит. V>Есть число 11110000 = F0. Необходимо прочитать справа налево num bit, начиная с first. V>Например: first = 2, num = 5, читаем 00111 = 7. V>Меня смущает цикл for и оператор if.
Не очень понял смысл цикла, если нужно со 2 по 5 бит, то просто
сдвигаем биты к началу и накладываем маску, что-то типа:
(value >> (first + 1)) & ((1 << (num- 1)) - 1)
V>Первое что приходит:
V>int v = 0;
V>for (int i = first; i < num + first; i++)
V> v = (v << 1) + (value & (1 << i)) ? 1 : 0;
Кстати в коде ошибка из-за приоритета операторов,
нужно в скобки обернуть выражение "(value & (1 << i)) ? 1 : 0",
чтобы все правильно считалось.
Плюс вполне возможно UB из-за работы с потенциально отрицательными
числами, лучше конечно использовать "unsigned int" в битовой арифметике.
Здравствуйте, Pzz, Вы писали: Pzz>Коды Хаффмана вычислительно тяжелы. Точно ли именно чтение их является узким местом в плане производительности?
В данный момент реализую декомпрессию статического Deflate. Коды Хаффмина вычисляются на основании таблицы кодов. Основная нагрузка прочитать 7-ми, 8-ми, 9-ти битовый код из потока. Коды Хаффмана пишутся справа налево.
Здравствуйте, Vladimir, Вы писали:
V>Подскажите алгоритм оптимального чтения LSB num бит. V>Есть число 11110000 = F0. Необходимо прочитать справа налево num bit, начиная с first. V>Например: first = 2, num = 5, читаем 00111 = 7. V>Первое что приходит:
V>int v = 0;
V>for (int i = first; i < num + first; i++)
V> v = (v << 1) + (value & (1 << i)) ? 1 : 0;
V>Меня смущает цикл for и оператор if. V>Спасибо.
Пришла идея: Записать обратный порядок бит, затем читать как обычно.
Здравствуйте, Vladimir, Вы писали:
V>Пришла идея: Записать обратный порядок бит, затем читать как обычно.[ccode]
Вы изобретаете свой "горный" велосипед или хотите сделать учебную реализацию уже сущестующего алгоритма упаковки?
Здравствуйте, kov_serg, Вы писали:
_>Здравствуйте, Vladimir, Вы писали:
V>>Пришла идея: Записать обратный порядок бит, затем читать как обычно.[ccode] _>Вы изобретаете свой "горный" велосипед или хотите сделать учебную реализацию уже сущестующего алгоритма упаковки?
Новое прочтение RFC1951 (Deflate).
SP>>unsigned int reverse_bits(unsigned int v)
SP>>{
SP>> return (v * 0x0202020202ULL & 0x010884422010ULL) % 1023;
SP>>}
SP>>
pva>Странно, почему не "& 0x3ff", а % 1023.
Эквивалентом "&0x3ff" было бы "%1024", а не "%1023". Внимательнее plz
pva> И почему ограничение в диаппазоне 10 бит.
Для более длинного нужны и константы длиннее. А этот фокус работает только со специально рассчитанными константами. В Hackersʼ Delight описана ещё пачка подобных.
pva>Как альтернатива — можно использовать предпросчитанную таблицу для реверса. Тогда все сведется к return (inversion[value] >> num) & ((1 << size) — 1);
