Целочисленный логарифм по основанию 2 за O(1)

Часто бывает нужно посчитать целую часть логарифма по основанию 2 от любого целого числа.

Решение в лоб это сделать цикл и в этом цикле постоянно делить число на два, пока оно не станет равно нулю. Сколько таких делений произошло, таково и значение логарифма. Да, такой способ рабочий и имеет право на жизнь, но я хочу показать как это можно сделать без всяких циклов и сложных конструкций.

Итак, мы хотим посчитать следующую формулу:

$\$\$display\$\$y\; =\; [log\_2(x)],\; x\; -\; целое,\; положительное\$\$display\$\$$

Решение

Для тех, кому не интересны рассуждения, я дам сразу готовые функции для вычисления логарифма:

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

uint32_t getBitCount_32(uint32_t x)
{
	x = (x & 0x55555555) + ((x >> 1) & 0x55555555);
	x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
	x = (x & 0x0F0F0F0F) + ((x >> 4) & 0x0F0F0F0F);
	x = (x & 0x00FF00FF) + ((x >> 8) & 0x00FF00FF);
	return (x & 0x0000FFFF) + (x >> 16);
}

uint32_t getLog2_32(uint32_t x)
{
    return getBitCount_32(getHighBit_32(x) - 1);
}

Объяснения

Для начала переведем число x в двоичную запись определенной длины.

Например, длины = 8, но это не принципиально и длина числа может быть любой.

А теперь вспомните, на чем основан перевод числа в двоичную запись. На том, чтобы представить число в виде суммы степеней двойки. Номер степени будет определять позицию бита, который равен 1. Например: $\$inline\$45\; =\; 32\; +\; 8\; +\; 4\; +\; 1\; =\; 2^5\; +\; 2^3\; +\; 2^2\; +\; 2^0\$inline\$$. Т.е. номера степеней 5, 3, 2 и 0. Это значит что 5-ый, 3-ий, 2-ой, 0-ой биты равен 1. Остальные биты между ними равны нулю. Отсчет битов начинается с правой стороны. Получилось, что $\$inline\$45\_\{10\}\; =\; 101101\_2\$inline\$$

Можно заметить, что перевод в двоичную запись тесно связан с возведением в степень, а логарифм это же операция обратная возведению в степень и равна она показателю степени.

$\$\$display\$\$2^y\; =\; x,\; y\; =\; log\_2(x)\$\$display\$\$$

Притом показатель степени, в которую нужно возвести 2, это номер единичного бита в двоичной записи. Получается, если найти номер единичного бита, то получим целую часть значения логарифма по основанию два. Например, если 32 = 100000, единичный бит стоит на 5 месте, поэтому логарифм равен 5.

Но поскольку единичных битов, может быть не 1, а несколько, то встает вопрос номер какого именно единичного бита брать, чтобы найти логарифм. Ответ — номер последнего единичного бита, начиная отсчет с правой стороны записи числа, потому что именно старшая степень двойки определяет целую часть логарифма, остальные составляют дробную часть логарифма.

Рассмотрим другой пример — число $\$inline\$45\_\{10\}\; =\; 101101\_2\$inline\$$. Последний единичный бит стоит на 5 месте, поэтому целая часть логарифма от 45 равна 5. и действительно $\$inline\$log\_2(45)=5.4919\$inline\$$. Дробную часть мы отбрасываем и остается 5.

Также работает и с другими числами.

В итоге мы получили, что целая часть логарифма равна номеру последнего единичного бита отсчитывая справа. Вопрос: как найти номер последнего единичного бита?

Для этого есть функции основанные на побитовых операциях, которые я нашел в книжке Г.Уоррена «Алгоритмические трюки для программистов».

• Округление до степени двойки в меньшую сторону (или выделение последнего единичного бита в двоичной записи числа). На самом деле можно округлять и в большую сторону, но тогда значение логарифма тоже будет округлено в большую сторону.
• Подсчет количества единичных битов в двоичной записи числа

Обе функции хорошо там описаны, а их код я привел ранее.

Используя эти две функции алгоритм вычисления алгоритма следующий:

1. Выделить последний единичный бит в числе. Теперь число стало записано в виде 100000
2. Вычесть единицу из полученного числа. Тогда число станет таким: 011111
3. Подсчитать количество единичных битов и это будет целое значение логарифма

Исключительная ситуация

У логарифма есть исключительная ситуация, когда x = 0. По идее такого алгоритма не существует (или в пределе он равен -∞). Однако, поскольку мы в программировании немного отходим от законов математики, то функции все равно работают даже когда на вход функции подается ноль. В таком случае значение логарифма будет равно 32 (если число 32-разрядное). Это происходит потому что функция округления до ближайшей степени двойки выдаст 0, потом мы из нуля вычитаем единицу и получаем число 0xFFFFFFFF, а единиц в таком числе 32 поэтому логарифм и будет равен 32.

Да, с точки зрения математики это некорректно, но есть случаи, когда это полезно с точки зрения программирования.

Подсчет длины двоичного кода

Применять подобную функцию вряд ли станут для вычисления именно математического логарифма, потому что чаще считают логарифмы от вещественных чисел, а не целых.
Однако подсчет длины двоичного кода — задача, которая на практике возникает чаще.

Пусть дан двоичный код определенной длины. Это может быть, например, путь в бинарном дереве. Если перед эти кодом записать единичный бит, то можно вычислять длину этого кода без использования вспомогательных переменных через взятие целочисленного логарифма.

Например, пусть дан код 0001110110. Он записан например в ячейку из 32 бит и нам нужно часто считать длину этого кода. Для этого припишем перед кодом дополнительный единичный бит.

Получим: 10001110110. И теперь можем смело считать длину этого кода через целочисленный логарифм, не храня отдельно длину этого кода где-то еще.

Если считать длину кода, где все нули, то функция выдаст длину = 32, что может быть некорректно, поэтому такую ситуацию надо предусмотреть. В каких-то ситуациях полезно, чтобы функция выдавала 32, а в каких-то, например, ноль.

Источники

1. Г. Уоррен «Алгоритмические трюки для программистов. Исправленное издание.», 2004