tejas - como calcular los m2 de un techo

Calcular techo de base de registro rápido 2

Question

¿Cuál es una forma rápida de calcular el (long int) ceiling(log_2(i)) , donde la entrada y la salida son enteros de 64 bits? Las soluciones para enteros con signo o sin signo son aceptables. Sospecho que la mejor manera será un método poco parecida a los que se encuentran here , pero en lugar de intentarlo me gustaría utilizar algo que ya está bien probado. Una solución general funcionará para todos los valores positivos.

Por ejemplo, los valores para 2,3,4,5,6,7,8 son 1,2,2,3,3,3,3

Editar: Hasta ahora, la mejor ruta parece ser calcular la base 2 del registro entero / suelo (la posición de la MSB) usando cualquier número de bithacks existentes rápidos o métodos de registro, y luego agregar uno si la entrada no es un poder de dos. La comprobación rápida en bit de las potencias de dos es (n&(n-1)) .

Edición 2: una buena fuente de logaritmos enteros y métodos de ceros a la izquierda son las Secciones 5-3 y 11-4 en Hacker''s Delight, de Henry S. Warren. Este es el tratamiento más completo que he encontrado.

Edición 3: esta técnica parece prometedora: https://stackoverflow.com/a/51351885/365478

Answer 1

El código siguiente es más simple y funcionará siempre que la entrada x> = 1. input clog2 (0) obtenga una respuesta indefinida (lo cual tiene sentido porque log (0) es infinito ...) Puede agregar la comprobación de errores para ( x == 0) si quieres:

unsigned int clog2 (unsigned int x)
{
    unsigned int result = 0;
    --x;
    while (x > 0) {
        ++result;
        x >>= 1;
    }

    return result;
}

Por cierto, el código para el piso de log2 es similar: (De nuevo, asumiendo x> = 1)

unsigned int flog2 (unsigned int x)
{
    unsigned int result = 0;
    while (x > 1) {
        ++result;
        x >>= 1;
    }

    return result;
}

Answer 2

El enfoque más rápido que conozco utiliza un log2 rápido que redondea hacia abajo, un ajuste incondicional combinado de valor de entrada antes y después para manejar el caso de redondeo como en lg_down() muestra a continuación.

/* base-2 logarithm, rounding down */
static inline uint64_t lg_down(uint64_t x) {
  return 63U - __builtin_clzl(x);
}

/* base-2 logarithm, rounding up */
static inline uint64_t lg_up(uint64_t x) {
  return lg_down(x - 1) + 1;
}

Básicamente, agregar 1 al resultado redondeado ya es correcto para todos los valores excepto las potencias exactas de dos (ya que en ese caso los enfoques de floor y ceil deben devolver la misma respuesta), por lo que es suficiente restar 1 del valor de entrada para manejar ese caso (no cambia la respuesta para los otros casos) y agregue uno al resultado.

Esto suele ser un poco más rápido que los enfoques que ajustan el valor al verificar explícitamente las potencias exactas de dos (por ejemplo, agregar un término !!(x & (x - 1)) ). Evita las comparaciones y las operaciones o ramas condicionales, es más probable que simplemente cuando está en línea, es más susceptible a la vectorización, etc.

Esto se basa en la funcionalidad de "contar bits __builtin_clzl " ofrecida por la mayoría de las CPU que utilizan el clang / icc / gcc incorporado __builtin_clzl , pero otras plataformas ofrecen algo similar (por ejemplo, el BitScanReverse intrínseco en Visual Studio).

Answer 3

El siguiente fragmento de código es una forma segura y portátil de extender los métodos de plain-C, como @dgobbi''s, para utilizar los intrínsecos del compilador cuando se compilan utilizando compiladores compatibles (Clang). Colocar esto en la parte superior del método hará que el método use el built-in cuando esté disponible. Cuando el built-in no está disponible, el método volverá al código C estándar.

#ifndef __has_builtin
#define __has_builtin(x) 0
#endif

#if __has_builtin(__builtin_clzll) //use compiler if possible
  return ((sizeof(unsigned long long) * 8 - 1) - __builtin_clzll(x)) + (!!(x & (x - 1)));
#endif

Answer 4

Encontrar la base de registro 2 de un entero (64 bits o cualquier otro bit) con salida entera es equivalente a encontrar el bit más significativo que se establece. ¿Por qué? Debido a que la base de registro 2 es cuántas veces puede dividir el número por 2 para llegar a 1.

Una forma de encontrar el MSB configurado es simplemente desplazar el bit hacia la derecha por 1 cada vez hasta que tenga 0. Otra forma más eficiente es realizar algún tipo de búsqueda binaria mediante máscaras de bits.

La parte del techo se calcula fácilmente comprobando si se han configurado otros bits distintos del MSB.

Answer 5

Este algoritmo ya se ha publicado, pero la siguiente implementación es muy compacta y debe optimizarse en código sin ramificación.

int ceil_log2(unsigned long long x)
{
  static const unsigned long long t[6] = {
    0xFFFFFFFF00000000ull,
    0x00000000FFFF0000ull,
    0x000000000000FF00ull,
    0x00000000000000F0ull,
    0x000000000000000Cull,
    0x0000000000000002ull
  };

  int y = (((x & (x - 1)) == 0) ? 0 : 1);
  int j = 32;
  int i;

  for (i = 0; i < 6; i++) {
    int k = (((x & t[i]) == 0) ? 0 : j);
    y += k;
    x >>= k;
    j >>= 1;
  }

  return y;
}


#include <stdio.h>
#include <stdlib.h>

int main(int argc, char *argv[])
{
  printf("%d/n", ceil_log2(atol(argv[1])));

  return 0;
}

Answer 6

La verdadera solución más rápida:

Un árbol de búsqueda binaria de 63 entradas. Estos son los poderes de 2 de 0 a 63. Función de generación única para crear el árbol. Las hojas representan la base de registro 2 de los poderes (básicamente, los números 1-63).

Para encontrar la respuesta, introduce un número en el árbol y navega hacia el nodo hoja que sea mayor que el elemento. Si el nodo de la hoja es exactamente igual, el resultado es el valor de la hoja. De lo contrario, el resultado es el valor de la hoja +1.

La complejidad se fija en O (6).

Answer 7

La búsqueda lineal ingenua puede ser una opción para los números enteros distribuidos uniformemente, ya que necesita un poco menos de 2 comparaciones en promedio (para cualquier tamaño entero).

/* between 1 and 64 comparisons, ~2 on average */
#define u64_size(c) (              /
    0x8000000000000000 < (c) ? 64  /
  : 0x4000000000000000 < (c) ? 63  /
  : 0x2000000000000000 < (c) ? 62  /
  : 0x1000000000000000 < (c) ? 61  /
...
  : 0x0000000000000002 < (c) ?  2  /
  : 0x0000000000000001 < (c) ?  1  /
  :                             0  /
)

Answer 8

Si está compilando procesadores de 64 bits en Windows, creo que esto debería funcionar. _BitScanReverse64 es una función intrínseca.

#include <intrin.h>
__int64 log2ceil( __int64 x )
{
  unsigned long index;
  if ( !_BitScanReverse64( &index, x ) )
     return -1LL; //dummy return value for x==0

  // add 1 if x is NOT a power of 2 (to do the ceil)
  return index + (x&(x-1)?1:0);
}

Para 32 bits, puede emular _BitScanReverse64, con 1 o 2 llamadas a _BitScanReverse. Verifique los 32 bits superiores de x, ((largo *) y x) [1], luego los 32 bits inferiores si es necesario, ((largo *) y x) [0].

Answer 9

Si puede limitarse a gcc, hay un conjunto de funciones integradas que devuelven el número de bits cero iniciales y se pueden usar para hacer lo que quiera con un poco de trabajo:

int __builtin_clz (unsigned int x)
int __builtin_clzl (unsigned long)
int __builtin_clzll (unsigned long long)

Answer 10

Si tiene flotadores de 80 bits o de 128 bits disponibles, cree ese tipo y luego lea los bits del exponente. Este enlace tiene detalles (para enteros de hasta 52 bits) y varios otros métodos:

http://graphics.stanford.edu/~seander/bithacks.html#IntegerLogIEEE64Float

Además, verifique la fuente de ffmpeg. Sé que tienen un algoritmo muy rápido. Incluso si no es directamente extensible a tamaños más grandes, puede hacer fácilmente algo como if (x>INT32_MAX) return fastlog2(x>>32)+32; else return fastlog2(x); if (x>INT32_MAX) return fastlog2(x>>32)+32; else return fastlog2(x);

Answer 11

Usando los comandos incorporados de gcc mencionados por @egosys, puedes construir algunas macros útiles. Para un cálculo rápido y aproximado del piso (log2 (x)), puede usar:

#define FAST_LOG2(x) (sizeof(unsigned long)*8 - 1 - __builtin_clzl((unsigned long)(x)))

Para un límite similar (log2 (x)), use:

#define FAST_LOG2_UP(x) (((x) - (1 << FAST_LOG2(x))) ? FAST_LOG2(x) + 1 : FAST_LOG2(x))

Este último se puede optimizar aún más utilizando más peculiaridades gcc para evitar la doble llamada al builtin, pero no estoy seguro de que lo necesite aquí.

Answer 12

#include "stdafx.h"
#include "assert.h"

int getpos(unsigned __int64 value)
{
    if (!value)
    {
      return -1; // no bits set
    }
    int pos = 0;
    if (value & (value - 1ULL))
    {
      pos = 1;
    }
    if (value & 0xFFFFFFFF00000000ULL)
    {
      pos += 32;
      value = value >> 32;
    }
    if (value & 0x00000000FFFF0000ULL)
    {
      pos += 16;
      value = value >> 16;
    }
    if (value & 0x000000000000FF00ULL)
    {
      pos += 8;
      value = value >> 8;
    }
    if (value & 0x00000000000000F0ULL)
    {
      pos += 4;
      value = value >> 4;
    }
    if (value & 0x000000000000000CULL)
    {
      pos += 2;
      value = value >> 2;
    }
    if (value & 0x0000000000000002ULL)
    {
      pos += 1;
      value = value >> 1;
    }
    return pos;
}

int _tmain(int argc, _TCHAR* argv[])
{    
    assert(getpos(0ULL) == -1); // None bits set, return -1.
    assert(getpos(1ULL) == 0);
    assert(getpos(2ULL) == 1);
    assert(getpos(3ULL) == 2);
    assert(getpos(4ULL) == 2);
    for (int k = 0; k < 64; ++k)
    {
        int pos = getpos(1ULL << k);
        assert(pos == k);
    }
    for (int k = 0; k < 64; ++k)
    {
        int pos = getpos( (1ULL << k) - 1);
        assert(pos == (k < 2 ? k - 1 : k) );
    }
    for (int k = 0; k < 64; ++k)
    {
        int pos = getpos( (1ULL << k) | 1);
        assert(pos == (k < 1 ? k : k + 1) );
    }
    for (int k = 0; k < 64; ++k)
    {
        int pos = getpos( (1ULL << k) + 1);
        assert(pos == k + 1);
    }
    return 0;
}