Calcule el techo rápido de la base logarítmica 2

11 minutos de lectura

avatar de usuario
kevinlawler

¿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? Se aceptan soluciones para enteros con o sin signo. Sospecho que la mejor manera será un método de giro de bits similar a los encontrados aquí, pero en lugar de intentar el mío, me gustaría usar 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 de registro de número entero/piso 2 (la posición del MSB) utilizando cualquier número de bithacks rápidos existentes o métodos de registro, y luego agregar uno si la entrada no es una potencia de dos. La verificación bit a bit rápida para potencias de dos es (n&(n-1)).

Edición 2: una buena fuente sobre logaritmos enteros y métodos de ceros a la izquierda son las Secciones 5-3 y 11-4 en Delicia de hacker por 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

  • Debe ser exactamente correcto para al menos todos los valores estrictamente mayores que uno y menores que un número grande, digamos 2^63 o 2^62.

    – Kevin Lawler

    17 de julio de 2010 a las 17:21

  • Por favor, vea mi respuesta a continuación. Pongo una explicación + el código que hará esto por ti.

    – Mahmud Al-Qudsi

    17 de julio de 2010 a las 17:31

  • En el pasado, generalmente usaba una combinación de tablas de búsqueda y cambios de bits, similares a los del enlace a la página de cambios de bits.

    – TechNeilogy

    17 de julio de 2010 a las 17:51


  • Si solo está tratando con valores positivos, una forma sencilla de manejar el redondeo es encontrar el conjunto de bits más significativo para ((x << 1) - 1). Necesitarías un caso especial x == 0y se desbordará si se establece el bit superior, pero este método puede ser más rápido que algunas de las otras técnicas de redondeo presentadas.

    – tomlogic

    2 de agosto de 2010 a las 20:33

  • en C++ 20 solo usa std::bit_ceildesafortunadamente esta pregunta es sobre C

    – phuclv

    23 de junio de 2021 a las 0:54

Este algoritmo ya se ha publicado, pero la siguiente implementación es muy compacta y debería optimizarse en código sin bifurcaciones.

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

  • He comentado esto como la mejor respuesta. Para cualquiera que siga la discusión, la razón por la que esta es actualmente la mejor respuesta es que las soluciones de lenguaje ensamblador son específicas de la plataforma.

    – Kevin Lawler

    11/03/2013 a las 20:25

  • ¿Alguna posibilidad de reescribir esto para usar nombres de variables informativos, para que sea posible entender cómo funciona?

    – Nic

    13 de diciembre de 2016 a las 0:41

  • por qué usas int en lugar de unsigned?

    – sebastián

    9 oct 2018 a las 18:42

  • @sebastian, la respuesta siempre estará entre 0 y 64, por lo que se puede usar cualquier tipo integral. Y dado que se puede usar cualquier tipo de entero, elegí el tipo predeterminado “int”.

    – dgobbi

    14 de agosto de 2020 a las 19:52

Si puede limitarse a gcc, hay un conjunto de funciones integradas que devuelven la cantidad de ceros 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)

avatar de usuario
tom sirgedas

Si está compilando para 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. Compruebe los 32 bits superiores de x, ((long*)&x)[1]luego los 32 bits inferiores si es necesario, ((long*)&x)[0].

  • Estaba pensando en algo más general que específico de Windows, pero hasta ahora el tuyo es el más cercano a la respuesta. Traducido, la idea es que existe un método bit a bit rápido para verificar si algo es una potencia de dos (que se muestra arriba). Podemos usar este método junto con un método de registro para determinar la posición del MSB para recuperar la respuesta.

    – Kevin Lawler

    18 de julio de 2010 a las 0:46


  • +1 y @highperformance: si solo tiene la intención de ejecutar su código en procesadores x86, puede hacer el escaneo de bits usted mismo con un poco de ensamblaje. (los BSR instrucciones, para ser específicos)

    – casablanca

    18 de julio de 2010 a las 1:40

  • @casablanca: es mucho mejor usar un intrínseco que el compilador entienda que usar un asm en línea real. Los compiladores pueden hacer una propagación constante a través de _BitScanReverse64 / __builtin_clzll, pero no a través de una instrucción inline-asm. Además, MSVC inline asm es basura total para envolver una sola instrucción. (GNU C inline asm funciona bien, pero aún no hay propagación constante). Además, __builtin_clzll es GNU C portátil y compilará lo que sea bueno en cualquier máquina de destino.

    – Peter Cordes

    28 mayo 2016 a las 17:40


avatar de usuario
abejaencuerda

El enfoque más rápido que conozco utiliza un método rápido log2 que redondea hacia abajo, ajuste incondicional combinado del valor de entrada antes y después para manejar el caso de redondeo como en lg_down() mostrado 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 hacia abajo ya es correcto para todos los valores, excepto para las potencias exactas de dos (ya que en ese caso el floor y ceil enfoques deberían 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 agregar uno al resultado.

Esto suele ser un poco más rápido que los enfoques que ajustan el valor verificando explícitamente las potencias exactas de dos (por ejemplo, agregando un !!(x & (x - 1)) término). Evita cualquier comparación y operaciones condicionales o bifurcaciones, es más probable que simplemente cuando se inserta, es más susceptible a la vectorización, etc.

Esto se basa en la funcionalidad de “recuento de bits iniciales” que ofrece la mayoría de las CPU que utilizan la función integrada clang/icc/gcc __builtin_clzlpero otras plataformas ofrecen algo similar (por ejemplo, el BitScanReverse intrínseco en Visual Studio).

Desafortunadamente, muchos devuelven la respuesta incorrecta para log(1)ya que eso conduce a __builtin_clzl(0) que es un comportamiento indefinido basado en la documentación de gcc. Por supuesto, la función general “contar ceros a la izquierda” tiene un comportamiento perfectamente definido en cero, pero el gcc incorporado se define de esta manera porque antes de la extensión BMI ISA en x86, habría estado usando el bsr instrucción que en sí mismo tiene un comportamiento indefinido.

Podría solucionar esto si sabe que tiene la lzcnt instrucción usando el lzcnt intrínseco directamente. La mayoría de las plataformas que no sean x86 nunca pasaron por el bsr error en primer lugar, y probablemente también ofrezcan métodos para acceder a su instrucción “contar ceros iniciales” si tienen uno.

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

  • La tabla de búsqueda eliminaría los últimos if cláusulas, cuatro o más dependiendo de la memoria disponible.

    – Kevin Lawler

    3 de agosto de 2010 a las 15:25


  • Para usar una tabla de búsqueda de 16 bits: declare global short getpos_lookup[1 << 16];. Rellenar previamente: int i; for(i=1;i<1<<16;i++) getpos_lookup[i]=log2(i); Entonces bajo el 16 caso comentar el 8/4/2/1 casos y poner pos += getpos_lookup[v];.

    – Kevin Lawler

    3 de agosto de 2010 a las 17:14


  • En realidad, ni siquiera estoy seguro de si mi versión es rápida. Usar un bucle for puede ser más rápido que cualquiera de los otros enfoques.

    – mal

    4 de agosto de 2010 a las 3:54

  • Hice algunas pruebas simples. Su método es apreciablemente más rápido que un bucle (por ejemplo, while(value>>=1)pos++;). Modificar su método para usar una tabla de búsqueda es un poco más rápido, pero no lo llamaría mucho más rápido. Para mis propósitos, su método ya es lo suficientemente rápido. Sin embargo, si alguien quisiera continuar mejorándolo, buscaría: 1. Reemplazar la detección de MSB con una llamada de registro (potencialmente usando #ifdef declaraciones de portabilidad). 2. emplear algunas heurísticas para explotar las distribuciones conocidas de la entrada (p. ej., el 90 % de los números entrantes están por debajo de 1000) 3. usar tablas de búsqueda

    – Kevin Lawler

    6 de agosto de 2010 a las 19:03

  • Cambiando a constantes como 0xFFFF0000FFFF0000, 0xFF00FF00FF00FF00, ... puedes quitar los turnos.

    – BCS

    13 de noviembre de 2012 a las 14:45

avatar de usuario
Alejandro Amelkin

Usando las funciones integradas de gcc mencionadas por @egosys, puede crear algunas macros útiles. Para un cálculo de piso rápido y aproximado (log2 (x)), puede usar:

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

Para un ceil(log2(x)) similar, 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 usando más peculiaridades de gcc para evitar la doble llamada al incorporado, pero no estoy seguro de que lo necesite aquí.

  • La tabla de búsqueda eliminaría los últimos if cláusulas, cuatro o más dependiendo de la memoria disponible.

    – Kevin Lawler

    3 de agosto de 2010 a las 15:25


  • Para usar una tabla de búsqueda de 16 bits: declare global short getpos_lookup[1 << 16];. Rellenar previamente: int i; for(i=1;i<1<<16;i++) getpos_lookup[i]=log2(i); Entonces bajo el 16 caso comentar el 8/4/2/1 casos y poner pos += getpos_lookup[v];.

    – Kevin Lawler

    3 de agosto de 2010 a las 17:14


  • En realidad, ni siquiera estoy seguro de si mi versión es rápida. Usar un bucle for puede ser más rápido que cualquiera de los otros enfoques.

    – mal

    4 de agosto de 2010 a las 3:54

  • Hice algunas pruebas simples. Su método es apreciablemente más rápido que un bucle (por ejemplo, while(value>>=1)pos++;). Modificar su método para usar una tabla de búsqueda es un poco más rápido, pero no lo llamaría mucho más rápido. Para mis propósitos, su método ya es lo suficientemente rápido. Sin embargo, si alguien quisiera continuar mejorándolo, buscaría: 1. Reemplazar la detección de MSB con una llamada de registro (potencialmente usando #ifdef declaraciones de portabilidad). 2. emplear algunas heurísticas para explotar las distribuciones conocidas de la entrada (p. ej., el 90 % de los números entrantes están por debajo de 1000) 3. usar tablas de búsqueda

    – Kevin Lawler

    6 de agosto de 2010 a las 19:03

  • Cambiando a constantes como 0xFFFF0000FFFF0000, 0xFF00FF00FF00FF00, ... puedes quitar los turnos.

    – BCS

    13 de noviembre de 2012 a las 14:45

El siguiente fragmento de código es una forma segura y portátil de extender los métodos de C sin formato, como @dgobbi, para usar los intrínsecos del compilador cuando se compilan con compiladores compatibles (Clang). Colocar esto en la parte superior del método hará que el método use el incorporado cuando esté disponible. Cuando el código integrado no está disponible, el método recurrirá 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

¿Ha sido útil esta solución?

Esta web utiliza cookies propias y de terceros para su correcto funcionamiento y para fines analíticos y para mostrarte publicidad relacionada con sus preferencias en base a un perfil elaborado a partir de tus hábitos de navegación. Al hacer clic en el botón Aceptar, acepta el uso de estas tecnologías y el procesamiento de tus datos para estos propósitos. Configurar y más información
Privacidad