c++ - online - jetbrain data

Cómo codificar un operador de módulo(%) en C/C++/Obj-C que maneja números negativos

Question

Una de mis mascotas odia los lenguajes derivados de C (como matemático) es que

(-1) % 8 // comes out as -1, and not 7

fmodf(-1,8) // fails similarly

¿Cuál es la mejor solución?

C ++ permite la posibilidad de plantillas y sobrecarga del operador, pero ambas son aguas turbias para mí. ejemplos recibidos con gratitud

Answer 1

Acabo de notar que Bjarne Stroustrup etiqueta % como el operador restante , no el operador de módulo.

Apuesto a que este es su nombre formal en las especificaciones de ANSI C & C ++, y que el abuso de la terminología se ha infiltrado. ¿Alguien sabe esto de hecho?

Pero si este es el caso, entonces la función fmodf () de C (y probablemente otras) es muy engañosa. deberían etiquetarse como fremf (), etc.

Answer 2

Aquí hay una función C que maneja un entero positivo o negativo O valores fraccionarios para AMBOS OPERANDS

#include <math.h>
float mod(float a, float N) {return a - N*floor(a/N);} //return in range [0, N)

Esta es seguramente la solución más elegante desde el punto de vista matemático. Sin embargo, no estoy seguro si es robusto en el manejo de enteros. A veces, los errores de coma flotante se arrastran al convertir int -> fp -> int.

Estoy usando este código para non-int s, y una función separada para int.

NOTA: ¡Necesito atrapar N = 0!

Código del probador:

#include <math.h>

float mod(float a, float N)
{
    float ret = a - N * floor (a / N);

    printf("%f.1 mod %f.1 = %f.1 /n", a, N, ret);

    return ret;
}

int main (char* argc, char** argv)
{
    printf ("fmodf(-10.2, 2.0) = %f.1  == FAIL! /n/n", x);

    float x;
    x = mod(10.2f, 2.0f);
    x = mod(10.2f, -2.0f);
    x = mod(-10.2f, 2.0f);
    x = mod(-10.2f, -2.0f);

    return 0;
}

(Nota: puede compilarlo y ejecutarlo directamente desde CodePad: http://codepad.org/UOgEqAMA )

Salida:

fmodf (-10.2, 2.0) = -0.20 == ¡FALLO!

10.2 mod 2.0 = 0.2
10.2 mod -2.0 = -1.8
-10.2 mod 2.0 = 1.8
-10.2 mod -2.0 = -0.2

Answer 3

Aquí hay una nueva respuesta a una pregunta anterior, basada en este documento de Microsoft Research y sus referencias.

Tenga en cuenta que a partir de C11 y C ++ 11 en adelante, la semántica de div ha convertido en truncamiento hacia cero (ver [expr.mul]/4 ). Además, para D dividido por d , C ++ 11 garantiza lo siguiente sobre el cociente qT y el resto rT

auto const qT = D / d;
auto const rT = D % d;
assert(D == d * qT + rT);
assert(abs(rT) < abs(d));
assert(signum(rT) == signum(D));

donde signum asigna a -1, 0, +1, dependiendo de si su argumento es <, ==,> que 0 (consulte esta sección Preguntas y respuestas para el código fuente).

Con la división truncada, el signo del resto es igual al signo del dividendo D , es decir, -1 % 8 == -1 . C ++ 11 también proporciona una función std::div que devuelve una estructura con los miembros quot y rem según la división truncada.

Hay otras definiciones posibles, por ejemplo, la llamada división con piso se puede definir en términos de la división truncada incorporada

auto const I = signum(rT) == -signum(d) ? 1 : 0;
auto const qF = qT - I;
auto const rF = rT + I * d;
assert(D == d * qF + rF);
assert(abs(rF) < abs(d));
assert(signum(rF) == signum(d));

Con la división con piso, el signo del resto es igual al signo del divisor d . En idiomas como Haskell y Oberon, existen operadores integrados para la división con piso. En C ++, necesitaría escribir una función usando las definiciones anteriores.

Otra forma es la división euclidiana , que también se puede definir en términos de la división truncada incorporada

auto const I = rT >= 0 ? 0 : (d > 0 ? 1 : -1);
auto const qE = qT - I;
auto const rE = rT + I * d;
assert(D == d * qE + rE);
assert(abs(rE) < abs(d));
assert(signum(rE) != -1);

Con la división euclidiana, el signo del resto siempre es positivo .

Answer 4

Creo que otra solución a este problema sería el uso de variables de tipo long en lugar de int.

Solo estaba trabajando en algún código donde el operador% devolvía un valor negativo que causaba algunos problemas (para generar variables aleatorias uniformes en [0,1] realmente no quieres números negativos :)), pero después de cambiar las variables a tipo largo, todo funcionaba sin problemas y los resultados coincidían con los que obtenía cuando ejecutaba el mismo código en python (importante para mí, ya que quería poder generar los mismos números "aleatorios" en varias plataformas).

Answer 5

En primer lugar, me gustaría señalar que ni siquiera se puede confiar en el hecho de que (-1) % 8 == -1 . lo único en lo que puede confiar es que (x / y) * y + ( x % y) == x . Sin embargo, si el resto es negativo está definido por la implementación .

Ahora, ¿por qué usar plantillas aquí? Una sobrecarga para ints y longs sería suficiente.

int mod (int a, int b)
{
   int ret = a % b;
   if(ret < 0)
     ret+=b;
   return ret;
}

y ahora puedes llamarlo como mod (-1,8) y parecerá ser 7.

Editar: Encontré un error en mi código. No funcionará si b es negativo. Entonces creo que esto es mejor:

int mod (int a, int b)
{
   if(b < 0) //you can check for b == 0 separately and do what you want
     return mod(a, -b);   
   int ret = a % b;
   if(ret < 0)
     ret+=b;
   return ret;
}

Referencia: C ++ 03, párrafo 5.6, cláusula 4:

El operador binario produce el cociente, y el operador binario% produce el resto de la división de la primera expresión por el segundo. Si el segundo operando de / o% es cero, el comportamiento no está definido; de lo contrario (a / b) * b + a% b es igual a a. Si ambos operandos son no negativos, el resto no es negativo; si no, el signo del resto está definido por la implementación .

Answer 6

Esta solución (para usar cuando mod es positivo) evita tomar operaciones negativas de división o resto todas juntas:

int core_modulus(int val, int mod)
{
    if(val>=0)
        return val % mod;
    else
        return val + mod * ((mod - val - 1)/mod);
}

Answer 7

La función general más simple para encontrar el módulo positivo sería esta: funcionaría tanto en valores positivos como negativos de x.

int modulo(int x,int N){
    return (x % N + N) %N;
}

Answer 8

La mejor solución para un matemático es usar Python.

La sobrecarga del operador C ++ tiene poco que ver con eso. No puede sobrecargar operadores para tipos incorporados. Lo que quieres es simplemente una función. Por supuesto, puede usar plantillas de C ++ para implementar esa función para todos los tipos relevantes con solo 1 pieza de código.

La biblioteca C estándar proporciona fmod , si recuerdo correctamente el nombre, para tipos de punto flotante.

Para los enteros, puede definir una plantilla de función C ++ que siempre devuelve un resto no negativo (correspondiente a la división euclidiana) como ...

#include <stdlib.h>  // abs

template< class Integer >
auto mod( Integer a, Integer b )
    -> Integer
{
    Integer const r = a%b;
    return (r < 0? r + abs( b ) : r);
}

... y solo escribe mod(a, b) lugar de a%b .

Aquí, el tipo Integer debe ser un tipo entero con signo.

Si desea el comportamiento matemático común donde el signo del resto es el mismo que el signo del divisor, puede hacer, por ejemplo,

template< class Integer >
auto floor_div( Integer const a, Integer const b )
    -> Integer
{
    bool const a_is_negative = (a < 0);
    bool const b_is_negative = (b < 0);
    bool const change_sign  = (a_is_negative != b_is_negative);

    Integer const abs_b         = abs( b );
    Integer const abs_a_plus    = abs( a ) + (change_sign? abs_b - 1 : 0);

    Integer const quot = abs_a_plus / abs_b;
    return (change_sign? -quot : quot);
}

template< class Integer >
auto floor_mod( Integer const a, Integer const b )
    -> Integer
{ return a - b*floor_div( a, b ); }

... con la misma restricción en Integer , que es un tipo firmado.

^{¹ Porque la división entera de Python se dirige hacia el infinito negativo.}

Answer 9

Oh, odio el diseño% para esto también ...

Puede convertir dividendos en unsigned de la siguiente manera:

unsigned int offset = (-INT_MIN) - (-INT_MIN)%divider

result = (offset + dividend) % divider

donde el desplazamiento es más cercano a (-INT_MIN) múltiplo del módulo, por lo tanto, sumar y restarlo no cambiará el módulo. Tenga en cuenta que tiene un tipo sin signo y el resultado será entero. Desafortunadamente no puede convertir correctamente los valores INT_MIN ... (- offset-1) ya que causan un desbordamiento arifmético. Pero este método tiene un avance de solo una aritmética adicional por operación (y sin condicionales) cuando se trabaja con divisor constante, por lo que se puede usar en aplicaciones similares a DSP.

Hay un caso especial, donde el divisor es 2 ^N (potencia de dos enteros), para lo cual el módulo se puede calcular usando aritmética simple y lógica bit a bit como

dividend&(divider-1)

por ejemplo

x mod 2 = x & 1
x mod 4 = x & 3
x mod 8 = x & 7
x mod 16 = x & 15

La forma más común y menos complicada es obtener módulo usando esta función (funciona solo con el divisor positivo):

int mod(int x, int y) {
    int r = x%y;
    return r<0?r+y:r;
}

Este es el resultado correcto si es negativo.

También puedes engañar:

(p% q + q)% q

Es muy corto pero usa dos% -s, que generalmente son lentos.

Answer 10

Para enteros esto es simple. Solo haz

(((x < 0) ? ((x % N) + N) : x) % N)

donde supongo que N es positivo y representable en el tipo de x . Su compilador favorito debería poder optimizar esto, de modo que termine en una sola operación de modificación en ensamblador.

Answer 11

Plantilla de ejemplo para C ++

template< class T >
T mod( T a, T b )
{
    T const r = a%b;
    return ((r!=0)&&((r^b)<0) ? r + b : r);
}

Con esta plantilla, el resto devuelto será cero o tendrá el mismo signo que el divisor (denominador) (el equivalente al redondeo hacia el infinito negativo), en lugar del comportamiento C ++ del resto siendo cero o teniendo el mismo signo que el dividendo ( numerador) (el equivalente al redondeo hacia cero).

Answer 12

Yo lo haría:

((-1)+8) % 8 

Esto suma el último número al primero antes de hacer el módulo dando 7 como se desee. Esto debería funcionar para cualquier número hasta -8. Para -9 agrega 2 * 8.

Answer 13

/* Warning: macro mod evaluates its arguments'' side effects multiple times. */ #define mod(r,m) (((r) % (m)) + ((r)<0)?(m):0)

... o simplemente acostúmbrate a conseguir un representante para la clase de equivalencia.

Answer 14

define  MOD(a, b)       ((((a)%(b))+(b))%(b))

Answer 15

unsigned mod(int a, unsigned b) {
    return (a >= 0 ? a % b : b - (-a) % b);
}