Что состоит в том, чтобы вычислить самый быстрый путь, число битов должно было сохранить число
Я пытаюсь оптимизировать некоторый бит упаковывающие и распаковывающие стандартные программы. Чтобы сделать упаковку, которую я должен вычислить, число битов должно было сохранить целочисленные значения. Вот текущий код.
if (n == -1) return 32;
if (n == 0) return 1;
int r = 0;
while (n)
{
++r;
n >>= 1;
}
return r;
6 ответов
Вы хотите определить целочисленную логарифмическую базу 2 числа (l = самый высокий набор бит). На странице Шона Андерсона "Bit Twiddling Hacks" есть несколько методов, начиная от очевидного подсчета битов в цикле и заканчивая версиями, использующими поиск по таблице. Обратите внимание, что большинство продемонстрированных методов необходимо будет немного изменить для работы с 64-разрядными целыми числами, если такая переносимость важна для вас.
Просто убедитесь, что любое переключение, которое вы используете для определения наивысшего набора битов, должно выполняться 'на беззнаковая версия числа, поскольку реализация компилятора может или не может подписывать расширение операции >> над значением со знаком.
Непереносимо, используйте код операции побитового сканирования-обратного, доступный в большинстве современных архитектур. Он представлен как внутренний в Visual C ++.
Переносимый код в вопросе не требует обработки крайнего случая. Почему вам нужен один бит для хранения 0? В любом случае я проигнорирую края проблемы. Таким образом, внутренности могут быть выполнены эффективно:
if (n >> 16) { r += 16; n >>= 16; }
if (n >> 8) { r += 8; n >>= 8; }
if (n >> 4) { r += 4; n >>= 4; }
if (n >> 2) { r += 2; n >>= 2; }
if (n - 1) ++r;
Вам нужно будет проверить время выполнения, чтобы оценить степень детализации, но я предполагаю, что выполнение 4 бита за раз с последующим возвратом к одному биту за раз ускорит процесс. Логические операции, вероятно, будут медленнее, чем логические / битовые операции.
if (n < 0) return 32;
int r = 0;
while (n && 0x7FFFFFF0) {
r+=4;
n >>= 4; }
while (n) {
r++;
n >>= 1; }
return r;
Вы пытаетесь найти самый старший бит. В некоторых архитектурах для этого есть специальная инструкция. Для тех, кто этого не делает, используйте метод поиска по таблице.
Создайте таблицу из 256 записей, в которой каждый элемент определяет самый верхний бит.
Либо переберите каждый байт числа, либо используйте несколько операторов if, чтобы найти ненулевой байт наивысшего порядка.
Я позволю тебе забрать остальное отсюда.
Выполните двоичный поиск вместо линейного.
if ((n >> 16) != 0)
{
r += 16;
n >>= 16;
}
if ((n >> 8) != 0)
{
r += 8;
n >>= 8;
}
if ((n >> 4) != 0)
{
r += 4;
n >>= 4;
}
// etc.
Если ваше оборудование поддерживает обратное сканирование битов, еще более быстрым подходом было бы написать вашу процедуру на языке ассемблера. Чтобы ваш код оставался переносимым, вы можете сделать
#ifdef ARCHITECTURE_WITH_BSR
asm // ...
#else
// Use the approach shown above
#endif
number_of_bits = log2(integer_number)
с округлением до большего целого числа.