while una que programa potencia para numeros numero mayor lea imprima hacer for con codigo ciclo calcule calcular c++ algorithm assembly

c++ - una - Algoritmo para encontrar la potencia más pequeña de dos que es mayor o igual a un valor dado



programa que calcule la potencia de un numero en c++ (16)

¿Qué tal una versión de plantilla recursiva para generar una constante de compilación?

template<uint32_t A, uint8_t B = 16> struct Pow2RoundDown { enum{ value = Pow2RoundDown<(A | (A >> B)), B/2>::value }; }; template<uint32_t A> struct Pow2RoundDown<A, 1> { enum{ value = (A | (A >> 1)) - ((A | (A >> 1)) >> 1) }; }; template<uint32_t A, uint8_t B = 16> struct Pow2RoundUp { enum{ value = Pow2RoundUp<((B == 16 ? (A-1) : A) | ((B == 16 ? (A-1) : A) >> B)), B/2>::value }; }; template<uint32_t A > struct Pow2RoundUp<A, 1> { enum{ value = ((A | (A >> 1)) + 1) }; };

Se puede usar así:

Pow2RoundDown<3221>::value, Pow2RoundUp<3221>::value

Esta pregunta ya tiene una respuesta aquí:

Necesito encontrar la potencia más pequeña de dos que sea mayor o igual a un valor dado. Hasta ahora, tengo esto:

int value = 3221; // 3221 is just an example, could be any number int result = 1; while (result < value) result <<= 1;

Funciona bien, pero se siente un poco ingenuo. ¿Hay un algoritmo mejor para ese problema?

EDITAR. Hubo algunas sugerencias agradables de ensamblador, así que estoy agregando esas etiquetas a la pregunta.

Aquí está mi favorito. Además del chequeo inicial para determinar si es inválido (<0, que podría omitir si supiera que solo tendría> = 0 números ingresados), no tiene bucles o condicionales, y por lo tanto superará a la mayoría de los otros métodos. Esto es similar a la respuesta de Erickson, pero creo que mi decrecimiento de x al comienzo y agregar 1 al final es un poco menos incómodo que su respuesta (y también evita el condicional al final).

/// Round up to next higher power of 2 (return x if it''s already a power /// of 2). inline int pow2roundup (int x) { if (x < 0) return 0; --x; x |= x >> 1; x |= x >> 2; x |= x >> 4; x |= x >> 8; x |= x >> 16; return x+1; }

Aquí hay una versión de plantilla de la técnica de cambio de bit.

template<typename T> T next_power2(T value) { --value; for(size_t i = 1; i < sizeof(T) * CHAR_BIT; i*=2) value |= value >> i; return value+1; }

Como el ciclo solo usa constantes, el compilador lo aplana. (Lo comprobé) La función también es a prueba de futuro.

Aquí hay uno que usa __builtin_clz. (También a prueba de futuro)

template<typename T> T next_power2(T value) { return 1 << ((sizeof(T) * CHAR_BIT) - __builtin_clz(value-1)); }

El siguiente código elimina repetidamente el bit más bajo hasta que el número sea una potencia de dos, luego dobla el resultado a menos que el número sea una potencia de dos para empezar. Tiene la ventaja de ejecutarse en un tiempo proporcional a la cantidad de bits configurados. Desafortunadamente, tiene la desventaja de requerir más instrucciones en casi todos los casos que el código en la pregunta o las sugerencias de ensamblaje. Lo incluyo solo para completarlo.

int nextPow(int x) { int y = x while (x &= (x^(~x+1))) y = x << 1; return y }

En el espíritu de Quake II 0x5f3759df y Bit Twyddling Hacks ''versión IEEE - esta solución alcanza en un doble para extraer el exponente como un medio para calcular el piso (lg2 ​​(n)). Es un poco más rápido que la solución aceptada y mucho más rápido que la versión IEEE de Bit Twiddling, ya que evita las matemáticas de coma flotante. Tal como está codificado, supone que un doble es un flotador real * 8 IEEE en una pequeña máquina endian.

int nextPow2(int n) { if ( n <= 1 ) return n; double d = n-1; return 1 << ((((int*)&d)[1]>>20)-1022); }

Editar: agregue la versión de ensamblaje x86 optimizada con la ayuda de un compañero de trabajo. Una ganancia de velocidad del 4%, pero aún un 50% más lenta que una versión bsr (6 segundos frente a 4 en mi computadora portátil para n = 1..2 ^ 31-2).

int nextPow2(int n) { if ( n <= 1 ) return n; double d; n--; __asm { fild n mov eax,4 fstp d mov ecx, dword ptr d[eax] sar ecx,14h rol eax,cl } }

En el hardware Intel, la instrucción BSR está cerca de lo que desea: encuentra el bit más significativo. Si necesita ser más preciso, entonces puede preguntarse si los bits restantes son precisamente cero o no. Tiendo a suponer que otras CPU tendrán algo así como BSR: esta es una pregunta que quieres que se responda para normalizar un número. Si su número es más de 32 bits, entonces haría un escaneo desde su DWORD más significativo para encontrar el primer DWORD con CUALQUIER conjunto de bits. Edsger Dijkstra probablemente comentaría que los "algoritmos" anteriores suponen que su computadora usa Dígitos Binarios, mientras que desde su elevada perspectiva "algorítmica" debería pensar en las máquinas de Turing o algo así - obviamente soy del estilo más pragmático.

Esto funciona y es realmente rápido (en mi procesador Intel Core 2 Duo de 64 bits a 2.66 GHz).

#include <iostream> int main(void) { int testinput,counter; std::cin >> testinput; while (testinput > 1) { testinput = testinput >> 1; counter++; } int finalnum = testinput << counter+1; printf("Is %i/n",finalnum); return 0; }

Lo probé en 3, 6 y 65496, y se dieron las respuestas correctas (4, 8 y 65536).

Lo siento si esto parece un poco arcano, estuve bajo la influencia de un par de horas de Doom justo antes de escribir. :)

Mi versión de lo mismo:

int pwr2Test(size_t x) { return (x & (x - 1))? 0 : 1; } size_t pwr2Floor(size_t x) { // A lookup table for rounding up 4 bit numbers to // the nearest power of 2. static const unsigned char pwr2lut[] = { 0x00, 0x01, 0x02, 0x02, // 0, 1, 2, 3 0x04, 0x04, 0x04, 0x04, // 4, 5, 6, 7 0x08, 0x08, 0x08, 0x08, // 8, 9, 10, 11 0x08, 0x08, 0x08, 0x08 // 12, 13, 14, 15 }; size_t pwr2 = 0; // The return value unsigned int i = 0; // The nybble interator for( i = 0; x != 0; ++i ) { // Iterate through nybbles pwr2 = pwr2lut[x & 0x0f]; // rounding up to powers of 2. x >>= 4; // (i - 1) will contain the } // highest non-zero nybble index. i = i? (i - 1) : i; pwr2 <<= (i * 4); return pwr2; } size_t pwr2Size(size_t x) { if( pwr2Test(x) ) { return x; } return pwr2Floor(x) * 2; }

Realmente no dices lo que quieres decir con "mejor algoritmo", pero como el que presentas es perfectamente claro (aunque algo defectuoso), supongo que buscas un algoritmo más eficiente.

Larry Gritz ha dado lo que probablemente sea el algoritmo c / c ++ más eficiente sin la sobrecarga de una tabla de búsqueda y sería suficiente en la mayoría de los casos (ver http://www.hackersdelight.org para algoritmos similares).

Como se mencionó en otras partes, la mayoría de las CPU tienen instrucciones de la máquina para contar el número de ceros iniciales (o devolver el bit ms configurado), pero su uso no es portátil y, en la mayoría de los casos, no vale la pena el esfuerzo.

Sin embargo, la mayoría de los compiladores tienen funciones "intrínsecas" que permiten el uso de las instrucciones de la máquina, pero de una manera más portátil.

Microsoft C ++ tiene _BitScanReverse () y gcc proporciona __builtin_clz () para hacer la mayor parte del trabajo de manera eficiente.

Sé que esto es cebo de abajo hacia abajo, pero si el número es lo suficientemente pequeño (como 8 o 16 bits) una búsqueda directa podría ser más rápida.

// fill in the table unsigned short tab[65536]; unsigned short bit = tab[i];

Es posible ampliarlo a 32 bits haciendo primero la palabra alta y luego la baja.

// unsigned long bitHigh = ((unsigned long)tab[(unsigned short)(i >> 16)]) << 16; unsigned long bitLow = 0; if (bitHigh == 0){ bitLow = tab[(unsigned short)(i & 0xffff)]; } unsigned long answer = bitHigh | bitLow;

Probablemente no sea mejor que el cambio o los métodos, pero tal vez podría extenderse a tamaños de palabra más grandes.

(En realidad, esto da el más alto de 1 bit. Tendría que cambiarlo a la izquierda por 1 para obtener la siguiente potencia más alta de 2.)

Su implementación no es ingenua, en realidad es la lógica, excepto que está mal: devuelve un valor negativo para números mayores que 1/2 del tamaño entero máximo.

Asumiendo que puede restringir los números al rango de 0 a 2 ^ 30 (para las entradas de 32 bits), funcionará muy bien, y mucho más rápido que cualquier función matemática que involucre logaritmos.

Los enteros sin signo funcionarían mejor pero terminarías con un bucle infinito (para números mayores que 2 ^ 31) ya que nunca puedes alcanzar 2 ^ 32 con el operador <<.

Una exploración de las posibles soluciones al problema estrechamente relacionado (es decir, redondeando hacia abajo en lugar de hacia arriba), muchas de las cuales son significativamente más rápidas que el enfoque ingenuo, está disponible en la página graphics.stanford.edu/~seander/bithacks.html#IntegerLogLookup , un recurso excelente para hacer los tipos de optimización. Estás buscando. La solución más rápida es usar una tabla de búsqueda con 256 entradas, que reduce el recuento total de operaciones a alrededor de 7, de un promedio de 62 (mediante una metodología de recuento de operaciones similar) para el enfoque ingenuo. Adaptar esas soluciones a su problema es una cuestión de una sola comparación e incremento.

Una función de registro arbitraria se puede convertir a una base de registro 2 dividiendo por el registro de 2:

$ /usr/local/pypy-1.9/bin/pypy Python 2.7.2 (341e1e3821ff, Jun 07 2012, 15:38:48) [PyPy 1.9.0 with GCC 4.4.3] on linux2 Type "help", "copyright", "credits" or "license" for more information. And now for something completely different: ``<arigato> yes but there is not much sense if I explain all about today''s greatest idea if tomorrow it''s completely outdated'''' >>>> import math >>>> print math.log(65535)/math.log(2) 15.9999779861 >>>> print math.log(65536)/math.log(2) 16.0 >>>>

Por supuesto, no será 100% preciso, ya que hay una aritmética de coma flotante involucrada.

amo el cambio.

me conformaré con

int bufferPow = 1; while ( bufferPow<bufferSize && bufferPow>0) bufferPow <<= 1;

de esa manera el ciclo siempre termina, y la parte después de && se evalúa casi nunca. Y no creo que dos líneas valen la pena llamar a una función. También puede hacer una larga, o corta, dependiendo de su juicio, y es muy legible. (Si bufferPow se vuelve negativo, con suerte su código principal saldrá rápidamente).

Por lo general, se calcula 2-potencia solo una vez al comienzo de un algoritmo, por lo que la optimización sería tonto de todos modos. Sin embargo, estaría interesado si alguien se aburre lo suficiente como para un concurso de velocidad ... usando los ejemplos anteriores y 255 256 257 .. 4195 4196 4197

pow (2, ceil (log2 (valor));

log2 (valor) = log (valor) / log (2);