La decisión frontal es hacer un bucle y en este bucle dividir constantemente el número por dos hasta que se convierta en cero. Cuántas divisiones de este tipo se han producido, ese es el valor del logaritmo. Sí, este método funciona y tiene derecho a la vida, pero quiero mostrar cómo se puede hacer sin ciclos ni estructuras complejas.
Entonces, queremos calcular la siguiente fórmula:
Decisión
Para aquellos que no están interesados en el razonamiento, les daré de inmediato funciones listas para calcular el 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);
}
Explicaciones
Primero, convierta el número x en una notación binaria de cierta longitud.
Por ejemplo, longitud = 8, pero esto no es importante y la longitud del número puede ser cualquiera.
Ahora recuerde en qué se basa la traducción de un número a una notación binaria. Representar el número como una suma de potencias de dos. El número de grado determinará la posición del bit, que es 1. Por ejemplo:... Aquellos. números de potencia 5, 3, 2 y 0. Esto significa que los bits 5, 3, 2, 0 son iguales a 1. El resto de los bits entre ellos son iguales a cero. Los bits comienzan desde el lado derecho. Resultó que
Se puede observar que la traducción a notación binaria está estrechamente relacionada con la exponenciación, y el logaritmo es el inverso de la exponenciación y es igual al exponente.
Además, el exponente al que debe elevar 2 es el número de un solo bit en una notación binaria. Resulta que si encuentra el número de un solo bit, entonces obtenemos la parte entera del valor del logaritmo en base dos. Por ejemplo, si 32 = 100000, el bit está en el quinto lugar, entonces el logaritmo es 5.
Pero como puede haber varios, no 1, surge la pregunta de cuál bit tomar para encontrar el logaritmo. La respuesta es el número del último bit, comenzando desde el lado derecho del registro del número, porque es la potencia más alta de dos la que determina la parte completa del logaritmo, el resto forma la parte fraccionaria del logaritmo.
Considere otro ejemplo: un número... El último bit está en el quinto lugar, por lo que la parte entera del logaritmo de 45 es 5. y de hecho... Descartamos la parte fraccionaria y dejamos 5.
También funciona con otros números.
Como resultado, obtuvimos que la parte entera del logaritmo es igual al número del último bit, contando desde la derecha. Pregunta: ¿cómo encontrar el número del último bit?
Para ello, existen funciones basadas en operaciones bit a bit, que encontré en el libro de G. Warren "Trucos algorítmicos para programadores".
- Redondear a una potencia de dos (o resaltar el último bit en la notación binaria de un número). De hecho, puede redondear hacia arriba, pero luego el valor del logaritmo también se redondeará.
- Contar el número de bits individuales en la notación binaria de un número
Ambas funciones están bien descritas allí, y di su código antes.
Usando estas dos funciones, el algoritmo para calcular el algoritmo es el siguiente:
- Seleccione el último bit del número. Ahora el número se escribió como 100000
- Reste uno del número resultante. Entonces el número será así: 011111
- Cuente el número de bits unitarios y este será el valor entero del logaritmo
Situación excepcional
El logaritmo tiene una situación excepcional cuando x = 0. En teoría, tal algoritmo no existe (o en el límite es igual a -∞). Sin embargo, dado que nos desviamos un poco de las leyes de las matemáticas en la programación, las funciones aún funcionan incluso cuando la entrada de la función es cero. En este caso, el valor del logaritmo será 32 (si el número es de 32 bits). Esto sucede porque la función de redondear a la potencia más cercana de dos dará 0, luego restamos uno de cero y obtenemos el número 0xFFFFFFFF, y hay 32 unidades en este número, por lo que el logaritmo será 32.
Sí, desde el punto de vista de las matemáticas, esto es incorrecto, pero hay casos, cuando es útil desde el punto de vista de la programación.
Contando la longitud de un código binario
Es poco probable que se utilice dicha función para calcular el logaritmo matemático, porque los logaritmos se consideran más a menudo a partir de números reales, no enteros.
Sin embargo, calcular la longitud de un código binario es una tarea más común en la práctica.
Sea un código binario de cierta longitud. Esto podría ser, por ejemplo, una ruta en un árbol binario. Si se escribe un solo bit delante de este código, entonces es posible calcular la longitud de este código sin usar variables auxiliares tomando un logaritmo entero.
Por ejemplo, démosle el código 0001110110. Está escrito, por ejemplo, en una celda de 32 bits y muchas veces necesitamos leer la longitud de este código. Para hacer esto, agregue un bit adicional antes del código.
Obtenemos: 10001110110. Y ahora podemos calcular con seguridad la longitud de este código a través del logaritmo entero, sin almacenar por separado la longitud de este código en otro lugar.
Si consideramos la longitud del código, donde están todos los ceros, entonces la función devolverá la longitud = 32, que puede ser incorrecta, por lo que se debe prever esta situación. En algunas situaciones, es útil que la función devuelva 32, y en otras, por ejemplo, cero.
Fuentes
- G. Warren “Trucos algorítmicos para programadores. Edición revisada. ", 2004