Logaritmo inteiro de base 2 em O (1)

Freqüentemente, é necessário calcular toda a parte do logaritmo de base 2 de qualquer inteiro.



A decisão direta é fazer um loop e, nesse loop, dividir constantemente o número por dois até que se torne zero. Quantas dessas divisões ocorreram, tal é o valor do logaritmo. Sim, esse método funciona e tem direito à vida, mas quero mostrar como isso pode ser feito sem ciclos e estruturas complexas.



Então, queremos calcular a seguinte fórmula:

$$

$$y = [log_2(x)], x - ,$$

Decisão

Para aqueles que não estão interessados ​​no raciocínio, darei imediatamente funções prontas para o cálculo do logaritmo:

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);
}

Explicações

Primeiro, vamos converter o número x em uma notação binária de certo comprimento.



Por exemplo, comprimento = 8, mas isso não é importante e o comprimento do número pode ser qualquer.



Agora lembre-se em que se baseia a tradução de um número para uma notação binária. Para representar o número como uma soma de potências de dois. O número do grau determinará a posição do bit, que é 1. Por exemplo:$$$45 = 32 + 8 + 4 + 1 = 2^5 + 2^3 + 2^2 + 2^0$... Essa. os números de potência 5, 3, 2 e 0. Isso significa que os bits 5, 3, 2 e 0 são iguais a 1. O resto dos bits entre eles são iguais a zero. Os bits começam do lado direito. Descobriu-se que$$$45_{10} = 101101_2$



Pode-se notar que a tradução em notação binária está intimamente relacionada à exponenciação, e o logaritmo é o inverso da exponenciação e é igual ao expoente.

$$

$$2^y = x, y = log_2(x)$$

Além disso, o expoente para o qual você precisa aumentar 2 é o número de um único bit em uma notação binária. Acontece que se encontrarmos o número de um único bit, obtemos a parte inteira do valor do logaritmo com base em dois. Por exemplo, se 32 = 100000, o bit um está na 5ª posição, então o logaritmo é 5.



Mas como pode haver vários uns, não 1, então surge a questão de qual bit usar para encontrar o logaritmo. A resposta é o número do último bit, partindo do lado direito do registro do número, pois é a maior potência de dois que determina toda a parte do logaritmo, os demais constituem a parte fracionária do logaritmo.



Considere outro exemplo - um número$$$45_{10} = 101101_2$... O último bit está na 5ª posição, então a parte inteira do logaritmo de 45 é 5. e de fato$$$log_2(45)=5.4919$... Descartamos a parte fracionária e deixamos 5.



Também funciona com outros números.



Como resultado, obtivemos que toda a parte do logaritmo é igual ao número do último bit, contando a partir da direita. Pergunta: como encontrar o número do último bit?



Para isso, existem funções baseadas em operações bit a bit, que encontrei no livro de G. Warren "Algorithmic tricks for programmers".

• Arredondando para uma potência de dois (ou destacando o último bit em uma notação binária de um número). Na verdade, você pode arredondar para cima, mas o valor do logaritmo também será arredondado para cima.
• Contando o número de bits únicos na notação binária de um número

Ambas as funções estão bem descritas aqui, e forneci seu código anteriormente.



Usando essas duas funções, o algoritmo para calcular o algoritmo é o seguinte:

1. Selecione o último bit do número. Agora, o número foi escrito como 100.000
2. Subtraia um do número resultante. Então, o número será assim: 011111
3. Conte o número de bits de unidade e este será o valor inteiro do logaritmo

Situação excepcional

O logaritmo tem uma situação excepcional quando x = 0. Em teoria, tal algoritmo não existe (ou no limite é igual a -∞). No entanto, como nos desviamos um pouco das leis da matemática na programação, as funções ainda funcionam mesmo quando a entrada da função é zero. Nesse caso, o valor do logaritmo será 32 (se o número for de 32 bits). Isso ocorre porque a função de arredondamento para a potência mais próxima de dois dará 0, então subtraímos um de zero e obtemos o número 0xFFFFFFFF, e há 32 unidades neste número, então o logaritmo será 32.



Sim, do ponto de vista da matemática, isso está incorreto, mas há casos, quando é útil do ponto de vista da programação.

Contando o comprimento de um código binário

É improvável que tal função seja usada para calcular o logaritmo matemático, porque os logaritmos são mais frequentemente considerados a partir de números reais, não inteiros.

No entanto, calcular o comprimento de um código binário é uma tarefa mais comum na prática.



Deixe um código binário de um certo comprimento ser fornecido. Pode ser, por exemplo, um caminho em uma árvore binária. Se um único bit for escrito na frente deste código, então é possível calcular o comprimento desse código sem usar variáveis ​​auxiliares, tomando um logaritmo inteiro.



Por exemplo, seja dado o código 0001110110. Está escrito, por exemplo, numa célula de 32 bits e muitas vezes precisamos de ler o comprimento deste código. Para fazer isso, adicione um bit adicional antes do código.



Receberemos: 10001110110. E agora podemos calcular com segurança o comprimento desse código através do logaritmo inteiro, sem armazenar separadamente o comprimento desse código em outro lugar.



Se considerarmos o comprimento do código, onde todos os zeros são, então a função retornará o comprimento = 32, o que pode estar incorreto, portanto esta situação deve ser prevista. Em algumas situações, é útil que a função retorne 32 e, em outras, por exemplo, zero.

Fontes

1. G. Warren “Truques Algorítmicos para Programadores. Edição revisada. ", 2004