Dado un numero calcular su potencia de 2

[zupervaca]

Hola estoy liado con la potencia de 2 por culpa de las texturas, mi problema es que no se si la pequeña rutina para calcular la potencia de 2 de un numero es lo mas optima posible:

Código [Seleccionar] Expand


int numero = 510;
int numeroPow2 = 2;
while( numeroPow2 < numero )
{
   numeroPow2 <<= 1;
}

¿Que os parece? hay algo mejor por ahi, tener en cuenta que las texturas no suelen ser muy grandes con lo que por ejemplo para 512 hace 9 pasos nada mas.

[ethernet]

dejando a un lado si la rutina es óptima o no te diré como calculo yo si una rutina es óptima:

- pienso el número de veces que voy a llamarla por frame
- si el número de veces es 0 entonces es óptima


moraleja: si la vas a llamar en una carga es mejor que gastes tu tiempo en optimizar otras cosas.

De cualquier modo con una búsqueda simple en google encuentras unas cuantas miles de respuestas, hasta en la wikipedia.

http://en.wikipedia.org/wiki/Power_of_two

[Pogacha]

Pienso exactamente lo mismo que que ethy.

No obstante, la solucion al problema generico es una busqueda binaria:
<Escrita al vuelo puede que tenga errores y que se pueda mejorar>

Código [Seleccionar] Expand

... ::LoadTexture( ... )
{
 ...
 // 6 and 13 by a supposed 64 min and 4096 max texture size
 texturewidth = 510;
 po2texurewidth = RoundLog2n(texturewidth, 6, 13)
 ...
}
...
int RoundLog2n(int n, int min, int max)
{
  ASSERT(n>0); // obviuslly it fails on zero
  ASSERT(min<max && min>=0 && max<=32);
   
  n--;
  int r = max;
  int l = 0;
  while(r>l+1)
  {
      int v = (r+l)/2;
      if((n>>v)==0)
      {
          if((n>>(v-1))!=0) return v;
          r = v;
      } else l = v;
  }
  return r;
}

[marcode]

Pues casi mejor precalcularlos en una lista, al fin y al cabo necesitarás como mucho 4096.

[zupervaca]

Por el momento me quedo con la que he hecho, mas que nada por que es para un caso especifico, las formulas que he visto por ahi siempre tienen que hacer la potencia y usar un vector es mas lento que rotar bits. No obstante gracias por las ideas :wink:

[Pogacha]

Pues casi mejor precalcularlos en una lista, al fin y al cabo necesitarás como mucho 4096.

Pero deberias estar usando la función mas de 4096 veces para que realmente ganaras algo ...
Aun que la generación de la tabla es trivial!

Código [Seleccionar] Expand

int t[4097], *k=t; for(int i=1; i<13; i++) for(int j=1<<(i-1); j; j--) *k++ = i;
Y casi que puedes hacer unos 12 memsets estaticos y optimizados.
Saludos!

[Pogacha]

Estos ejercicios ademas de darme placer ( de algunas manera sexual ) me ayudan a aprender mejores tecnicas de programación y por eso que de ves en cuando me obseciono con ellos un poco.
Hace una semana requería de una función que me calcule una potencia de 2 de forma ultra rapida, y no me valia una tabla pues debia ser inline así que dejo aca el resultado del experimento:

Para referencia la busqueda lineal (32 iteraciones max)

Código [Seleccionar] Expand

inline unsigned int Log2(unsigned int x) {
unsigned int i = 0;
while(x>1) { x>>=1; ++i; }
return i;
}

Luego lo logico era la busqueda binaria:

Código [Seleccionar] Expand

inline unsigned int Log2(unsigned int x) {
unsigned int f=0, s=32;
while(s) {
s>>=1;
if(x > 1<<(f+s)) f+=s;
}
return f;
}

Finalmente haciendo un poco de unroll

Código [Seleccionar] Expand

inline unsigned int Log2(const unsigned int x) {
register unsigned int l=0;
if(x >= 1<<16) l|=16;
if(x >= (1<<8)<<l) l|=8;
if(x >= (1<<4)<<l) l|=4;
if(x >= (1<<2)<<l) l|=2;
if(x >= (1<<1)<<l) l|=1;
return l;
}

Si fuera una funcion estatica, podriamos expandir las ramas para evitar el calculo del pivot.

Finalmente lo hacemos en limpio en ASM
Entrada en ebx, salida en eax, modificados eax y edx.

Código [Seleccionar] Expand

xor eax, eax
cmp ebx, 65536
jb N1
or al, 16

N1: mov edx, 256
shl edx, al
cmp ebx, edx
jb N2
or al, 8

N2: mov edx, 16
shl edx, al
cmp ebx, edx
jb N3
or al, 4

N3: mov edx, 4
shl edx, al
cmp ebx, edx
jb N4
or al, 2

N4: mov edx, 2
shl edx, al
cmp ebx, edx
jb N5
or al, 1

N5:
Casi no hay paridad :( así que son casi como 25 cyclos quieras o no.
Algun gurú del asm como Fiero podrian mejorarlo tal vez.

Saludos!