BitNeBolt
@BitNeBolt

Как узнать степень числа, которая является средним арифметическим степеней двух чисел?

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

Например, новый элемент добавляется на индекс 18 (куча ориентирована на минимум),
в массиве находятся следующие значения
a[18] = 1.5
a[9] = 9
a[4] = 2.5
a[2] = 2
a[1] = 1


Мне нужно сравнить a[4] и a[18]. Степень 4 - это среднее арифметическое степеней 2 в числе 1 и 18 (округленную вниз). Как можно узнать эту степень?
  • Вопрос задан
  • 61 просмотр
Решения вопроса 1
wataru
@wataru Куратор тега Алгоритмы
Разработчик на С++, экс-олимпиадник.
Странное задание. Какая польза от этого сокращения сравнений, если всего в результате вставки переместится до O(log n) элементов?

Но, если так надо, то вам нужно для каждого числа сначала узнать номер старшего ненулевого бита (most significat bit - MSB), и потом сдвинуть верхнее число вправо на половину разницы в позициях старших битов.

1 = 0000001b, msb = 0
18 = 0010010b, msb = 4

Разность - 4 разряда. Значит, надо сдвигать на 2 разряда вправо:
18 >> 2= 0010010b >> 2 = 00100b = 4

Еще пример: для 4 и 18 msb были бы 2 и 4, разность -2. Сдвинув 18 на 2/2=1 разряд вправо, вы бы получили 9.

Чтобы эта оптимизация давала хоть какую-то пользу, надо находить msb очень быстро. Или предподсчитайте их для всех возможных индексов, или надейтесь, что в вашем языке есть встроенная функция, которая вызывает нужную инструкцию процессора, типа __builtin_clz.

Еще можно подсчитать msb только один раз для правой границы бинпоиска, а потом просто помнить его, ведь у средней точки - это среднее арифметическое (левая граница изначально 1 - у нее msb = 0). А потом в процессе бинпоиска надо просто хранить msb для двух границ и заменять известным значением середины один из концов.

Для предподсчета просто в цикле задавайте msb[i] = msb[i/2] + 1;
Ответ написан
Пригласить эксперта
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы