Что состоит в том, чтобы вычислить самый быстрый путь, число битов должно было сохранить число

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

if (n == -1) return 32;
if (n == 0) return 1;
int r = 0;
while (n)
{
    ++r;
    n >>= 1;
}
return r;
9
задан hippietrail 17 April 2011 в 09:51
поделиться

6 ответов

Вы хотите определить целочисленную логарифмическую базу 2 числа (l = самый высокий набор бит). На странице Шона Андерсона "Bit Twiddling Hacks" есть несколько методов, начиная от очевидного подсчета битов в цикле и заканчивая версиями, использующими поиск по таблице. Обратите внимание, что большинство продемонстрированных методов необходимо будет немного изменить для работы с 64-разрядными целыми числами, если такая переносимость важна для вас.

Просто убедитесь, что любое переключение, которое вы используете для определения наивысшего набора битов, должно выполняться 'на беззнаковая версия числа, поскольку реализация компилятора может или не может подписывать расширение операции >> над значением со знаком.

6
ответ дан 4 December 2019 в 08:00
поделиться

Непереносимо, используйте код операции побитового сканирования-обратного, доступный в большинстве современных архитектур. Он представлен как внутренний в 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;
9
ответ дан 4 December 2019 в 08:00
поделиться

Вам нужно будет проверить время выполнения, чтобы оценить степень детализации, но я предполагаю, что выполнение 4 бита за раз с последующим возвратом к одному биту за раз ускорит процесс. Логические операции, вероятно, будут медленнее, чем логические / битовые операции.

if (n < 0) return 32;
int r = 0;
while (n && 0x7FFFFFF0) {
  r+=4;
  n >>= 4; }
while (n) {
  r++;
  n >>= 1; }
return r;
3
ответ дан 4 December 2019 в 08:00
поделиться

Вы пытаетесь найти самый старший бит. В некоторых архитектурах для этого есть специальная инструкция. Для тех, кто этого не делает, используйте метод поиска по таблице.

Создайте таблицу из 256 записей, в которой каждый элемент определяет самый верхний бит.

Либо переберите каждый байт числа, либо используйте несколько операторов if, чтобы найти ненулевой байт наивысшего порядка.

Я позволю тебе забрать остальное отсюда.

5
ответ дан 4 December 2019 в 08:00
поделиться

Выполните двоичный поиск вместо линейного.

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
3
ответ дан 4 December 2019 в 08:00
поделиться
number_of_bits = log2(integer_number)

с округлением до большего целого числа.

1
ответ дан 4 December 2019 в 08:00
поделиться
Другие вопросы по тегам:

Похожие вопросы: