Pull to refresh

Алгоритмы поиска старшего бита

Reading time 3 min
Views 39K
Здесь я хочу рассказать и обсудить несколько алгоритмов для нахождения старшего единичного бита числа.

На всякий случай, поясню: старшим битом называется единичный бит числа, отвечающий за самую большую степень двойки. Иными словами, это самая большая степень двойки, не превосходящая числа. Чтобы избежать многих случаев, будем здесь считать, что мы имеем дело с натуральным числом в пределах от 1 до 2^31 — 1 включительно. Кроме того, чтобы не слишком углубляться в теорию вероятности, будем считать, что число, в котором требуется определить старший бит, с одинаковой вероятностью будет любым из возможных чисел.

Для начала, рассмотрим самый простой, первым приходящий в голову алгоритм. Давайте переберём все степени двойки, и выберем из них максимальную, которая не превосходит числа. Здесь, очевидно, можно воспользоваться монотонностью этого свойства, то есть тем, что если какая-то степень двойки не превосходит числа, то и меньше степени и подавно не превосходят. Поэтому, это метод можно написать очень просто:

int bit1(int x) {
   int t = 1 << 30;
   while (x < t) t >>= 1;
   return t;
}


(тут я использую java, но, думаю, понятно будет всем, в силу нативности кода)

Посмотрим, как долго он может работать. Если считать, что число с одинаковой вероятностью оказывается любым из обозначенного промежутка, то, с вероятностью 1/2, а именно, если х окажется не меньше, чем 2^30, цикл while не отработает ни одного раза. С вероятностью 1/4, а именно, если х находится в промежутке от 2^29 до 2^30 — 1, цикл отработает один раз. И так далее. Несложно понять, что это означает, что цикл отрабатывает в среднем полраза. Что весьма неплохо в среднем, но плохо в худшем случае: на числе х=1 цикл отработает все тридцать раз.

Следующий алгоритм лишён этой неприятности; а точнее, он лишён неопределённости во времени работы вообще. Я для начала продемонстрирую код, а потом объясню принцип работы.

int bit2(int x) {
   x |= x >> 1;
   x |= x >> 2;
   x |= x >> 4;
   x |= x >> 8;
   x |= x >> 16;
   return x - (x >> 1);
}


Итак, пусть дано число х=000001bbbbb (я не следил за необходимым количеством бит в числе, b означает любой бит). Тогда
x          == 000001bbbbb
x >> 1     == 0000001bbbb
x | x >> 1 == 0000011bbbb

Таким образом, первое действие вслед за старшей единичкой, где бы она не оказалась, ставит следующую. Второе, как можно понять, ставит за этими двумя ещё две. Третее — ещё 4 (если есть, куда ставить). И так далее. Таким образом, в числе все биты после старшего оказываются единичными. Тогда понятно, что x — (x >> 1) выдаёт нам правильный ответ.

Третий алгоритм не совсем лишён произвола во времени работы, но в худшем случае, тем не менее, работает значительно быстрее первого. Он основан на бинпоиске. Попробуем взять средний бит, например, 16-тый, и сформируем условие на то, будет старший бит младшей 16-го, или нет. Понятно, что таким условием будет x < 1 << 16. Значит, надо сохранить результат проверки:

int t = 1;
if (x >= 1 << 16) t <<= 16;


ну а дальше, конечно, надо проверить, нельзя ли подвинуть t ещё на 8 бит, потом на 4, на 2, и на 1:

int bit3(int x) {
   int t = 1;
   if (x >= t << 16) t <<= 16;
   if (x >= t << 8) t <<= 8;
   if (x >= t << 4) t <<= 4;
   if (x >= t << 2) t <<= 2;
   if (x >= t << 1) t <<= 1;
   return t;
}


Итак, второй и третий алгоритмы работают в среднем дольше, чем первый (что и подтверждает непосредственный эксперимент, а так же то, что третий алгоритм работает чуть-чуть быстрее второго), но в худшем случае они работают быстрее.
Кроме того, надо заметить одну вещь. В первом методе используется магическая константа 1 << 30. Её использование основано на том, что мы знаем, что число с равной вероятностью бывает любым от 1 до 2^31 — 1. Если числа бывают меньшими, то можно уменьшить и константу. Например, если числа от 1 до 100000, то можно начинать с int t = 1 << 17. Но что если мы не знаем, какими будут числа, для которых используется метод? Если они теоретически могут быть равными до 2^31 — 1, а на самом деле они будут не больше 1000. Тогда нам придётся поставить int t = 1 << 30, и этот метод (как, опять же, подтверждают эксперименты), будет работать значительно дольше, чем последующие два. То есть, первый метод не только может иногда работать долго, но и может оказаться, что он в среднем работает дольше. Время его работы может оказаться непредсказуемым. Тогда как все эти непряитности совершенно не относятся к остальным двум методам.

Наконец, ещё один нюанс. Три вышеперечисленных алгоритма возвращают именно степень двойки — число вида 2^k. Но что, если нам надо найти именно k? Первый и третий методы легко преобразуются так, чтобы выдавать показатель степени, а не саму степень. Первый алгоритм начинает работать несколько быстрее, третий — чуть-чуть дольше. Но второй алгоритм к этому совершенно не приспособлен. Таким образом, второй алгоритм тоже имеет свой специфический минус.

P.S. Первый алгоритм слишком очевиден, чтобы ставить вопрос об авторстве, второй подсказан мне одним односительно широко известным олимпиадным программистом, а третий я придумал сам, хотя убеждён, что далеко не единствнным и уж точно не первым.
Tags:
Hubs:
+37
Comments 101
Comments Comments 101

Articles