Limpio, algoritmo eficiente para envolver enteros en C++

Question

/** 
    * Returns a number between kLowerBound and kUpperBound 
    * e.g.: Wrap(-1, 0, 4); // Returns 4 
    * e.g.: Wrap(5, 0, 4); // Returns 0  
    */ 
int Wrap(int const kX, int const kLowerBound, int const kUpperBound) 
{ 
    // Suggest an implementation? 
} 

Answer 1

El signo de a % b solo se define si a y b son ambos negativos.

int Wrap(int kX, int const kLowerBound, int const kUpperBound) 
{ 
    int range_size = kUpperBound - kLowerBound + 1; 

    if (kX < kLowerBound) 
     kX += range_size * ((kLowerBound - kX)/range_size + 1); 

    return kLowerBound + (kX - kLowerBound) % range_size; 
} 

Answer 2

para el KX negativo, se puede añadir:

int temp = kUpperBound - kLowerBound + 1; 
while (kX < 0) kX += temp; 
return kX%temp + kLowerBound; 

Answer 3

En realidad, desde el -1% 4 devuelve -1 en todos los sistemas incluso he estado en, la solución de mod simple no funciona. Me gustaría probar:

int range = kUpperBound - kLowerBound +1; 
kx = ((kx - kLowerBound) % range) + range; 
return (kx % range) + kLowerBound; 

si kx es positivo, mod, añadir variedad y la espalda mod, deshaciendo el complemento. Si kx es negativo, modifica, agrega rango que lo hace positivo, luego mod de nuevo, que no hace nada.

Answer 4

Lo siguiente debe trabajar de forma independiente de la aplicación del operador mod:

int range = kUpperBound - kLowerBound + 1; 
kx = ((kx-kLowerBound) % range); 
if (kx<0) 
    return kUpperBound + 1 + kx; 
else 
    return kLowerBound + kx; 

una ventaja sobre otras soluciones es decir, que utiliza sólo un único% (es decir, división), que hace que sea bastante eficiente.

Nota (Off Topic):

Es un buen ejemplo, por qué a veces es conveniente definir los intervalos con el ser cota superior siendo el primer elemento no está en el rango (como por iteradores STL .. .). En este caso, ambos "+1" desaparecerían.

Answer 5

que sugeriría esta solución:

int Wrap(int const kX, int const kLowerBound, int const kUpperBound) 
{ 
    int d = kUpperBound - kLowerBound + 1; 
    return kLowerBound + (kX >= 0 ? kX % d : -kX % d ? d - (-kX % d) : 0); 
} 

La lógica if-then-else del operador ?: se asegura de que los dos operandos de % son no negativos.

Answer 6

Una respuesta que tiene cierta simetría y también hace que sea obvio que cuando kX está en rango, se devuelve sin modificaciones.

int Wrap(int const kX, int const kLowerBound, int const kUpperBound) 
{ 
    int range_size = kUpperBound - kLowerBound + 1; 

    if (kX < kLowerBound) 
     return kX + range_size * ((kLowerBound - kX)/range_size + 1); 

    if (kX > kUpperBound) 
     return kX - range_size * ((kX - kUpperBound)/range_size + 1); 

    return kX; 
} 

Answer 7

Daría un punto de entrada al caso más común lowerBound = 0, upperBound = N-1. Y llame a esta función en el caso general. No se realiza ningún cálculo de modulación cuando ya estoy dentro del alcance. Asume superior> = menor, o n> 0.

int wrapN(int i,int n) 
{ 
    if (i<0) return (n-1)-(-1-i)%n; // -1-i is >=0 
    if (i>=n) return i%n; 
    return i; // In range, no mod 
} 

int wrapLU(int i,int lower,int upper) 
{ 
    return lower+wrapN(i-lower,1+upper-lower); 
} 

Answer 8

solución más rápida, menos flexibles: Tome ventaja de los tipos de datos nativos que harán envoltura en el hardware.

El absoluta más rápido método para envolver enteros sería para asegurarse de que sus datos están a escala en INT8/Int16/int32 o cualquier tipo de datos nativo. ¡Entonces cuando necesites tus datos para envolver el tipo de datos nativo se hará en el hardware! Muy indoloro y órdenes de magnitud más rápidos que cualquier implementación de envoltura de software vista aquí.

como un estudio de caso de ejemplo:

he encontrado que esto es muy útil cuando necesito una rápida implementación de seno/coseno implementarse utilizando una consulta de tabla para una sen/cos aplicación.Básicamente, haces escalar tus datos de forma que INT16_MAX sea pi e INT16_MIN sea -pi. Entonces tienes que estás listo para ir.

Como nota al margen, la ampliación de sus datos será añadir un poco coste de computación en la delantera finito que por lo general se ve algo como:

int fixedPoint = (int)(floatingPoint * SCALING_FACTOR + 0.5) 

No dude en int cambio de otra cosa que desee, como int8_t/int16_t/int32_t.

---

siguiente solución más rápida, más flexible: La operación mod es lento en su lugar si es posible tratar de utilizar máscaras de bits!

La mayoría de las soluciones que desnate son funcionalmente correctas ... pero dependen de la operación de modificación.

La operación de modificación es muy lenta porque esencialmente está haciendo un hardware division. La explicación de los legos de por qué el mod y la división son lentos es equiparar la operación de división a algún pseudo-código for(quotient = 0;inputNum> 0;inputNum -= divisor) { quotient++; } (def de quotient and divisor). Como puede ver, la división de hardware puede ser rápida si es un número bajo en relación con el divisor ... pero la división también puede ser ser terriblemente lenta si es mucho mayor que el divisor.

Si puede escalar sus datos a una potencia de dos, puede usar una máscara de bits que se ejecutará en un ciclo (en el 99% de todas las plataformas) y su velocidad de mejora será de aproximadamente un orden de magnitud (en al menos 2 o 3 veces más rápido).

código C para implementar envolver:

#define BIT_MASK (0xFFFF) 
int wrappedAddition(int a, int b) { 
    return (a + b) & BIT_MASK; 
} 
int wrappedSubtraction(int a, int b) { 
    return (a - b) & BIT_MASK; 
} 

Siéntete libre de la #define algo que se ejecuta de tiempo. Y no dude en ajustar la máscara de bits para que sea la potencia de dos que necesite. Al igual que 0xFFFFFFFF o el poder de dos, decide implementarlo.

---

p.s. Recomiendo leer sobre el procesamiento de punto fijo cuando se juega con condiciones de envoltura/desbordamiento. Sugiero la lectura:

Fixed-Point Arithmetic: An Introduction by Randy Yates August 23, 2007

Answer 9

me he enfrentado a este problema también. Esta es mi solución.

template <> int mod(const int &x, const int &y) { 
    return x % y; 
} 
template <class T> T mod(const T &x, const T &y) { 
    return ::fmod((T)x, (T)y); 
} 
template <class T> T wrap(const T &x, const T &max, const T &min = 0) { 
    if(max < min) 
     return x; 
    if(x > max) 
     return min + mod(x - min, max - min + 1); 
    if(x < min) 
     return max - mod(min - x, max - min + 1); 
    return x; 
} 

No sé si es bueno, pero yo había pensado que me gustaría compartir desde que me dirigí aquí cuando se hace una búsqueda en Google sobre este problema y encontré las soluciones anteriores que carecen de mis necesidades. =)

Answer 10

No olvides esta publicación. :)

¿Esto es bueno?

int Wrap(N,L,H){ 
    H=H-L+1; return (N-L+(N<L)*H)%H+L; 
} 

Esto funciona para entradas negativas, y todos los argumentos puede ser negativo, siempre y cuando L es menos de H.

Antecedentes ... (Tenga en cuenta que H aquí es la variable reutilizado, ajustado a originales H-L+1)

He estado usando (N-L)%H+L al aumentar, pero a diferencia de Lua, que utilicé antes de empezar a aprender C hace unos meses, esto NO funcionaría si utilizaba entradas por debajo del límite inferior, no importa las entradas negativas. (Lua está construido en C, pero no sé lo que está haciendo, y es probable que no sería rápido ...)

decidí agregar +(N<L)*H hacer (N-L+(N<L)*H)%H+L, como C parece definirse de tal manera que true = 1 y falso = 0. Funciona bastante bien para mí, y parece responder la pregunta original perfectamente. Si alguien sabe cómo hacerlo sin el operador MOD% para hacerlo deslumbrantemente rápido, hágalo. No necesito velocidad en este momento, pero lo haré, sin dudas.

EDIT:

Esa función falla si N es inferior en más de un LH-L+1 pero esto no lo hace:

int Wrap(N,L,H){ 
    H-=L; return (N-L+(N<L)*((L-N)/H+1)*++H)%H+L; 
} 

Creo que se rompería en el extremo negativo de la gama de enteros en cualquier sistema, pero debería funcionar para la mayoría de las situaciones prácticas. Agrega una multiplicación adicional y una división, pero todavía es bastante compacto.

(Esta edición es sólo para la terminación, debido a que se me ocurrió una manera mucho mejor, en una nueva entrada en este hilo.)

Crow.

Answer 11

Mi otra publicación se volvió desagradable, toda esa multiplicación y división 'correctiva' se salió de control. Después de mirar el post de Martín Stettner, y en mis propias condiciones de partida de (N-L)%H+L, se me ocurrió esto:

int Wrap(N,L,H){ 
    H=H-L+1; N=(N-L)%H+L; if(N<L)N+=H; return N; 
} 

En el extremo negativo de la gama de enteros que se rompe como mi otro lo haría, pero será más rápido, y es mucho más fácil de leer, y evita la otra maldad que se arrastró en él.

Cuervo.

Answer 12

¿Por qué no utilizar los métodos de extensión.

public static class IntExtensions 
{ 
    public static int Wrap(this int kX, int kLowerBound, int kUpperBound) 
    { 
     int range_size = kUpperBound - kLowerBound + 1; 

     if (kX < kLowerBound) 
      kX += range_size * ((kLowerBound - kX)/range_size + 1); 

     return kLowerBound + (kX - kLowerBound) % range_size; 
    } 
} 

Uso: currentInt = (++currentInt).Wrap(0, 2);

Answer 13

soluciones Personalmente he encontrado que este tipo de funciones que sean más limpias si es exclusiva gama y divisor se limita a valores positivos.

int ifloordiv(int x, int y) 
{ 
    if (x > 0) 
     return x/y; 
    if (x < 0) 
     return (x + 1)/y - 1; 
    return 0 
} 

int iwrap(int x, int y) 
{ return x - y * ifloordiv(x, y); 
} 

Integrado.

int iwrap(int x, int y) 
{ 
    if (x > 0) 
     return x % y; 
    if (x < 0) 
     return (x + 1) % y + y - 1; 
    return 0; 
} 

Mismas familias. Por qué no?

int ireflect(int x, int y) 
{ 
    int z = iwrap(x, y*2); 
    if (z < y) 
     return z; 
    return y*2-1 - z; 
} 

int ibandy(int x, int y) 
{ 
    if (y != 1) 
     return ireflect(abs(x + x/(y - 1)), y); 
    return 0; 
} 

funcionalidad a distancia puede ser implementado para todas las funciones con,

// output is in the range [min, max). 
int func2(int x, int min, int max) 
{ 
    // increment max for inclusive behavior. 
    assert(min < max); 
    return func(x - min, max - min) + min; 
}