tipos - ¿Cómo hacer un entero log2() en C++?

string en c

Question

En las bibliotecas estándar de C ++, encontré solo un método de registro de coma flotante. Ahora uso log para encontrar el nivel de un índice en un árbol binario ( floor(2log(index)) ).

Código (C ++):

int targetlevel = int(log(index)/log(2));

Me temo que para algunos de los elementos de borde (los elementos con valor 2 ^ n) log devolverá n-1.999999999999 en lugar de n.0. ¿Este miedo es correcto? ¿Cómo puedo modificar mi declaración para que siempre devuelva una respuesta correcta?

Answer 1

Logaritmo de enteros de base 2

Esto es lo que hago para enteros sin signo de 64 bits. Esto calcula el piso del logaritmo de base 2, que es equivalente al índice del bit más significativo. Este método es increíblemente rápido para números grandes porque usa un ciclo desenrollado que se ejecuta siempre en log₂64 = 6 pasos.

Esencialmente, lo que hace es restar cuadrados progresivamente más pequeños en la secuencia {0 ≤ k ≤ 5: 2 ^ (2 ^ k)} = {2³², 2¹⁶, 2⁸, 2⁴, 2², 2¹} = {4294967296, 65536, 256 , 16, 4, 2, 1} y suma los exponentes k de los valores restados.

int uint64_log2(uint64_t n)
{
#define S(k) if (n >= (UINT64_C(1) << k)) { i += k; n >>= k; }
int i = -(n == 0); S(32); S(16); S(8); S(4); S(2); S(1); return i;
#undef S
}

Tenga en cuenta que esto devuelve -1 si se le da una entrada inválida de 0 (que es lo que la inicial -(n == 0) está buscando). Si nunca espera invocarlo con n == 0 , puede sustituir int i = 0; para el inicializador y agregar assert(n != 0); en la entrada a la función.

Logaritmo de enteros de base 10

Los logaritmos enteros de base 10 se pueden calcular de forma similar, con el cuadrado más grande para probar que es 10¹⁶ porque log₁₀2⁶⁴ .2 19.2659 ...

int uint64_log10(uint64_t n)
{
#define S(k, m) if (n >= UINT64_C(m)) { i += k; n /= UINT64_C(m); }
int i = -(n == 0);
S(16,10000000000000000); S(8,100000000); S(4,10000); S(2,100); S(1,10);
return i;
#undef S
}

Answer 2

¿Qué tan profundo proyectas que sea tu árbol? Puede establecer un rango de digamos ... +/- 0.00000001 al número para forzarlo a un valor entero.

De hecho, no estoy seguro de que golpees un número como 1.99999999 porque tu log2 no debería perder precisión al calcular 2 ^ n valores (desde rondas de puntos flotantes a la potencia más cercana de 2).

Answer 3

Esta es una publicación anterior, pero comparto mi algoritmo de una línea:

unsigned uintlog2(unsigned x)
{
unsigned l;
for(l=0; x>1; x>>=1, l++);
return l;
}

Answer 4

Esta función determina cuántos bits se requieren para representar el intervalo numérico: [0..maxvalue].

unsigned binary_depth( unsigned maxvalue )
{
int depth=0;
while ( maxvalue ) maxvalue>>=1, depth++;
return depth;
}

Al restar 1 del resultado, obtienes floor(log2(x)) , que es una representación exacta de log2(x) cuando x es una potencia de 2.

x y y-1
0 0 -1
1 1 0
2 2 1
3 2 1
4 3 2
5 3 2
6 3 2
7 3 2
8 4 3

Answer 5

Esta función que escribí here

// The ''i'' is for int, there is a log2 for double in stdclib
inline unsigned int log2i( unsigned int x )
{
unsigned int log2Val = 0 ;
// Count push off bits to right until 0
// 101 => 10 => 1 => 0
// which means hibit was 3rd bit, its value is 2^3
while( x>>=1 ) log2Val++; // div by 2 until find log2. log_2(63)=5.97, so
// take that as 5, (this is a traditional integer function!)
// eg x=63 (111111), log2Val=5 (last one isn''t counted by the while loop)
return log2Val ;
}

Answer 6

Esto ha sido propuesto en los comentarios anteriores. Usando los builtins de gcc:

static inline int log2i(int x) {
assert(x > 0);
return sizeof(int) * 8 - __builtin_clz(x) - 1;
}
static void test_log2i(void) {
assert_se(log2i(1) == 0);
assert_se(log2i(2) == 1);
assert_se(log2i(3) == 1);
assert_se(log2i(4) == 2);
assert_se(log2i(32) == 5);
assert_se(log2i(33) == 5);
assert_se(log2i(63) == 5);
assert_se(log2i(INT_MAX) == sizeof(int)*8-2);
}

Answer 7

Esto no es estándar ni necesariamente portátil, pero funcionará en general. No sé cuán eficiente es.

Convierta el índice entero en un número de coma flotante de suficiente precisión. La representación será exacta, suponiendo que la precisión es suficiente.

Busque la representación de los números de punto flotante de IEEE, extraiga el exponente y realice los ajustes necesarios para encontrar el registro de la base 2.

Answer 8

Hay respuestas similares arriba. Esta respuesta

1. Funciona con números de 64 bits
2. Le permite elegir el tipo de redondeo y
3. Incluye código de prueba / muestra

Funciones:

 static int floorLog2(int64_t x)
{
assert(x > 0);
return 63 - __builtin_clzl(x);
}
static int ceilLog2(int64_t x)
{
if (x == 1)
// On my system __builtin_clzl(0) returns 63. 64 would make more sense
// and would be more consistent. According to this result
// can get even stranger and you should just avoid __builtin_clzl(0).
return 0;
else
return floorLog2(x-1) + 1;
}

Código de prueba:

for (int i = 1; i < 35; i++)
std::cout<<"floorLog2("<<i<<") = "<<floorLog2(i)
<<", ceilLog2("<<i<<") = "<<ceilLog2(i)<<std::endl;

Answer 9

Nunca he tenido ningún problema con la precisión de punto flotante en la fórmula que está usando (y una comprobación rápida de números del 1 al 2 ³¹ - 1 no encontró errores), pero si está preocupado, puede usar esta función en cambio, que devuelve los mismos resultados y es aproximadamente un 66% más rápido en mis pruebas:

int HighestBit(int i){
if(i == 0)
return -1;
int bit = 31;
if((i & 0xFFFFFF00) == 0){
i <<= 24;
bit = 7;
}else if((i & 0xFFFF0000) == 0){
i <<= 16;
bit = 15;
}else if((i & 0xFF000000) == 0){
i <<= 8;
bit = 23;
}
if((i & 0xF0000000) == 0){
i <<= 4;
bit -= 4;
}
while((i & 0x80000000) == 0){
i <<= 1;
bit--;
}
return bit;
}

Answer 10

Puede usar este método en su lugar:

int targetlevel = 0;
while (index >>= 1) ++targetlevel;

Nota: esto modificará el índice. Si lo necesita sin cambios, cree otro int temporal.

El caso de esquina es cuando el índice es 0. Probablemente debería verificarlo por separado y lanzar una excepción o devolver un error si index == 0.

Answer 11

Reescribiendo la respuesta de Todd Lehman para ser más genérico:

#include <climits>
template<typename N>
constexpr N ilog2(N n) {
N i = 0;
for (N k = sizeof(N) * CHAR_BIT; 0 < (k /= 2);) {
if (n >= static_cast<N>(1) << k) { i += k; n >>= k; }
}
return i;
}

Clang con -O3 desenrolla el ciclo:

0000000100000f50 pushq %rbp
0000000100000f51 movq %rsp, %rbp
0000000100000f54 xorl %eax, %eax
0000000100000f56 cmpl $0xffff, %edi
0000000100000f5c setg %al
0000000100000f5f shll $0x4, %eax
0000000100000f62 movl %eax, %ecx
0000000100000f64 sarl %cl, %edi
0000000100000f66 xorl %edx, %edx
0000000100000f68 cmpl $0xff, %edi
0000000100000f6e setg %dl
0000000100000f71 leal (,%rdx,8), %ecx
0000000100000f78 sarl %cl, %edi
0000000100000f7a leal (%rax,%rdx,8), %eax
0000000100000f7d xorl %edx, %edx
0000000100000f7f cmpl $0xf, %edi
0000000100000f82 setg %dl
0000000100000f85 leal (,%rdx,4), %ecx
0000000100000f8c sarl %cl, %edi
0000000100000f8e leal (%rax,%rdx,4), %eax
0000000100000f91 xorl %edx, %edx
0000000100000f93 cmpl $0x3, %edi
0000000100000f96 setg %dl
0000000100000f99 leal (%rdx,%rdx), %ecx
0000000100000f9c sarl %cl, %edi
0000000100000f9e leal (%rax,%rdx,2), %ecx
0000000100000fa1 xorl %eax, %eax
0000000100000fa3 cmpl $0x1, %edi
0000000100000fa6 setg %al
0000000100000fa9 orl %ecx, %eax
0000000100000fab popq %rbp

Cuando n es constante, el resultado se calcula en tiempo de compilación.

Answer 12

Si está en una plataforma ish reciente x86 o x86-64 (y probablemente lo sea), use la instrucción bsr que devolverá la posición del bit más alto establecido en un entero sin signo. Resulta que esto es exactamente lo mismo que log2 (). Aquí hay una breve función C o C ++ que invoca bsr usando ASM en línea:

#include <stdint.h>
static inline uint32_t log2(const uint32_t x) {
uint32_t y;
asm ( "/tbsr %1, %0/n"
: "=r"(y)
: "r" (x)
);
return y;
}

Answer 13

Si está utilizando C ++ 11 puede hacer que esta sea una función constexpr:

constexpr std::uint32_t log2(std::uint32_t n)
{
return (n > 1) ? 1 + log2(n >> 1) : 0;
}

Answer 14

Si solo desea una operación de registro ₂ entero rápido, la siguiente función mylog2() lo hará sin tener que preocuparse por la precisión del punto flotante:

#include <limits.h>
static unsigned int mylog2 (unsigned int val) {
if (val == 0) return UINT_MAX;
if (val == 1) return 0;
unsigned int ret = 0;
while (val > 1) {
val >>= 1;
ret++;
}
return ret;
}
#include <stdio.h>
int main (void) {
for (unsigned int i = 0; i < 20; i++)
printf ("%u -> %u/n", i, mylog2(i));
putchar (''/n'');
for (unsigned int i = 0; i < 10; i++)
printf ("%u -> %u/n", i+UINT_MAX-9, mylog2(i+UINT_MAX-9));
return 0;
}

El código anterior también tiene un arnés de prueba pequeño para que pueda verificar el comportamiento:

0 -> 4294967295
1 -> 0
2 -> 1
3 -> 1
4 -> 2
5 -> 2
6 -> 2
7 -> 2
8 -> 3
9 -> 3
10 -> 3
11 -> 3
12 -> 3
13 -> 3
14 -> 3
15 -> 3
16 -> 4
17 -> 4
18 -> 4
19 -> 4
4294967286 -> 31
4294967287 -> 31
4294967288 -> 31
4294967289 -> 31
4294967290 -> 31
4294967291 -> 31
4294967292 -> 31
4294967293 -> 31
4294967294 -> 31
4294967295 -> 31

UINT_MAX para un valor de entrada de 0 como indicación de un resultado indefinido, por lo que es algo que debe verificar (ningún entero válido sin signo tendrá un logaritmo tan alto).

Por cierto, hay algunos hacks increíblemente rápidos para hacer exactamente esto (encontrar el bit más alto establecido en el número de complemento de 2) disponible desde here . No recomendaría su uso a menos que la velocidad sea esencial (prefiero la legibilidad), pero debes saber que existen.

Answer 15

int targetIndex = floor(log(i + 0.5)/log(2.0));