¿Cómo hacer un número entero log2() en C++?

Question

En las bibliotecas estándar de C++ solo encontré un método de registro de punto 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), el registro devolverá n-1.999999999999 en lugar de n.0.¿Es correcto este miedo?¿Cómo puedo modificar mi declaración para que siempre devuelva una respuesta correcta?

Answer 1

Puede utilizar este método en lugar:

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

Nota: esto va a modificar el índice. Si lo necesita sin cambios, crear otro int temporal.

El caso esquina es cuando el índice es 0. Es probable que debe comprobar por separado y lanzar una excepción o devuelve un error si el índice == 0.

Answer 2

Si usted está en un reciente x 86-ish o plataforma x86-64 (y probablemente lo están), utilice la instrucción bsr que devolverá la posición del bit más alto en conjunto un entero sin signo. Resulta que esto es exactamente lo mismo que log2 (). Aquí es una función C ++ corto C o 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 3

Si lo que desea es un número entero de registro rápido ₂ operación, la siguiente función será mylog2() hacerlo sin tener que preocuparse de coma flotante de precisión:

#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 pequeño instrumento de prueba para que pueda comprobar 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

Se volverá UINT_MAX para un valor de entrada de 0 como una indicación de un resultado no definido, así que eso es algo que usted debe comprobar si hay (sin entero sin signo válida tendrá un logaritmo que alto).

Por cierto, hay algunos trucos increíblemente rápida para hacer exactamente esto (Encontrar el bit más alto puesto en un número complementario del 2), disponible en aquí . Yo no recomendaría su uso a menos que la velocidad es de la esencia (yo prefiero la legibilidad yo) pero deben ser conscientes de que existen.

Answer 4

Base-2 Entero Logaritmo

Esto es lo que hago para enteros sin signo de 64 bits. Esto calcula el suelo de la logaritmo en base 2, que es equivalente al índice del bit más significativo. Este método es smokingly rápido para un gran número, ya que utiliza un bucle de desenrollado que se ejecuta siempre en log₂64 = 6 pasos.

Esencialmente, lo que hace es resta de distancia progresivamente cuadrados más pequeños en la secuencia {0 ≤ k ≤ 5: 2 ^ (2 ^ k)} = {2³², 2¹⁶, 2⁸, 2⁴, 2², 2¹} = {4294967296, 65 536, 256, 16, 4, 2, 1} y resume 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 les da la entrada no válida de 0 (que es lo que el -(n == 0) inicial está comprobando). Si no esperas lo debe invocar con n == 0, puede poner int i = 0; para la inicialización y añadir assert(n != 0); en la entrada a la función.

Base-10 Entero Logaritmo

Base-10 logaritmos de números enteros se pueden calcular utilizando de manera similar - con el cuadrado más grande para probar ser 10¹⁶ porque log₁₀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 5

Esto se ha propuesto en las observaciones anteriores. El uso de órdenes internas 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 6

Nunca he tenido ningún problema con coma flotante de precisión en la fórmula que está utilizando (y una revisión rápida de números del 1 al 2 ³¹ - 1 detecta ningún error), pero si usted está preocupado, puede utilizar esta función en lugar, que devuelve los mismos resultados y se trata de 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 7

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

Answer 8

Esto no es necesariamente estándar o portátil, pero lo hará en el trabajo en general. No sé qué tan eficiente es.

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

Busque la representación de los números de punto flotante IEEE, extraer el exponente, y hacer los ajustes necesarios para encontrar el logaritmo en base 2.

Answer 9

Si estás usando C ++ 11 se puede hacer de esto una función constexpr:

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

Answer 10

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 stackoverflow 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 11

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

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

Al restar 1 al resultado se obtiene floor(log2(x)), que es un exacto representacion de log2(x) cuando x es una potencia de 2.

Xyy-1
00-1
110
221
321
432
532
632
732
843

Answer 12

¿Qué tan profundo es lo que proyectas su árbol a ser? Se podría establecer un rango de +/- digamos ... 0,00000001 al número de forzarlo a un valor entero.

No estoy realmente seguro de que va a golpear un número como 1,99999999 porque su log2 no debe perder cierta precisión en el cálculo de 2 ^ n valores (Desde rondas de punto flotante a la fuente más cercana de 2).

Answer 13

Esta función escribí aquí

// 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 14

Esta es una entrada antigua pero comparten mi algoritmo de una sola línea:

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

Answer 15

La reescritura Todd Lehman 's respuesta sea 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 bucle:

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, resultado se calcula en tiempo de compilación.

Answer 16

Dada la forma en números de punto flotante de trabajo (crudamente, mantisa * 2 ^ exponente), entonces cualquier número hasta 2 ^ 127 que es una potencia de 2 estará representado exactamente sin error.

Esto da una solución trivial sino hacky - interpretar el patrón de bits del número de coma flotante como un entero, y simplemente mira el exponente. Esta es la solución de David Thornley anteriormente.

float f = 1;
for (int i = 0; i < 128; i++)
{
    int x = (*(int*)(&f)>>23) - 127;
    int l = int(log(f) / log(2));

    printf("i = %d, log = %d, f = %f quick = %d\n",
        i, l, f, x);
    f *= 2;
}

No es cierto que cualquier número entero se puede representar como un flotador - sólo aquellos con menos bits que la mantisa puede representar. En los flotadores de 32 bits, es decir 23 bits pena.