Como codificar um operador de módulo (%) em C / C ++ / Obj-C que lida com números negativos

86

Um dos meus ódios prediletos de linguagens derivadas de C (como matemático) é que

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

fmodf(-1,8) // fails similarly

Qual é a melhor solução?

C ++ permite a possibilidade de modelos e sobrecarga de operador, mas ambos são águas turvas para mim. exemplos recebidos com gratidão.

P i
fonte
1
Eu não acho que isso seja uma "duplicata" de stackoverflow.com/questions/828092/… sob a definição oficial. Não é verdade que as respostas dessa pergunta possam ser mescladas com as outras, porque essa pergunta só pergunta sobre módulo, não também sobre divisão. Mas eu acho que essa questão foi respondida por aquela, então está perto. Minha resposta já está aí, FWIW.
Steve Jessop
Talvez esse tópico deva ser dividido, pois faz duas perguntas distintas. a melhor maneira de fazer isso é fazer novamente a pergunta da divisão separadamente e, em seguida, apontar para essa resposta. Deixo isso para quem entende melhor os mecanismos deste site.
P i
3
@Pi owhere é %dito ser o módulo ... é o resto .
obataku,
1
Aqui está outro tópico que é uma "duplicata" de: stackoverflow.com/questions/1082917/… Apenas para referência sobre este %problema.
leetNightshade
Se você estiver apenas dividindo poderes de dois, pode ser uma ideia melhor usar e:(-1) & 8 == 7
Henricus V.

Respostas:

74

Em primeiro lugar, gostaria de observar que você nem pode confiar no fato disso (-1) % 8 == -1. a única coisa em que você pode confiar é isso (x / y) * y + ( x % y) == x. No entanto, se o restante é negativo ou não, é definido pela implementação .

Agora, por que usar modelos aqui? Uma sobrecarga de ints e longs bastaria.

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

e agora você pode chamá-lo como mod (-1,8) e parecerá ser 7.

Edit: Eu encontrei um bug no meu código. Não funcionará se b for negativo. Então eu acho que é melhor:

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

Referência: C ++ 03 parágrafo 5.6 cláusula 4:

O binário / operador produz o quociente, e o operador binário% produz o resto da divisão da primeira expressão pela segunda. Se o segundo operando de / ou% for zero, o comportamento é indefinido; caso contrário (a / b) * b + a% b é igual a a. Se ambos os operandos forem não negativos, o restante será não negativo; caso contrário, o sinal do restante é definido pela implementação .

Armen Tsirunyan
fonte
2
@Ohmu: Sim, isso está no padrão C ++. <quote> Para operandos integrais, o operador / produz o quociente algébrico com qualquer parte fracionária descartada; se o quociente a / b for representável no tipo do resultado, (a / b) * b + a% b é igual a. </quote>
Ben Voigt
5
-1. Já se passaram 11 anos desde que essa implementação foi definida. ISO 9899: 1999 definiu e, infelizmente, escolheu a definição ruim.
R .. GitHub PARAR DE AJUDAR O ICE
3
@Armen: Você convenientemente excluiu a nota de rodapé <quote> ... a divisão de inteiros segue as regras definidas no padrão ISO Fortran, ISO / IEC 1539: 1991, em que o quociente é sempre arredondado para zero </quote>. O novo padrão C ++ atualiza esse comportamento de "preferencial" para obrigatório, assim como Fortran e C.
Ben Voigt
2
@Armen: A especificação antiga está quebrada, mas o defeito é diferente do problema do sinal, e é fácil passar despercebido até você olhar para o novo texto. C ++ 03 não tinha "se o quociente a / b é representável no tipo do resultado", o que causa problemas para INT_MIN / -1(em implementações de complemento de dois). De acordo com a especificação antiga, -32768 % -1pode ter que avaliar para -65536(que também não está no intervalo do tipo de 16 bits, eca!) Para que a identidade seja mantida.
Ben Voigt
1
re "No entanto, se o resto é negativo ou não, é definido pela implementação.", C ++ 11 garante que a divisão inteira gira para 0.
Viva e hth. - Alf
12

Aqui está uma função C que lida com valores inteiros positivos OU negativos OU fracionários para AMBOS OS OPERANDOS

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

Esta é certamente a solução mais elegante do ponto de vista matemático. No entanto, não tenho certeza se ele é robusto para lidar com números inteiros. Às vezes, erros de ponto flutuante aparecem ao converter int -> fp -> int.

Estou usando este código para non-int s e uma função separada para int.

NOTA: é necessário interceptar N = 0!

Código do testador:

#include <math.h>
#include <stdio.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", fmodf(-10.2, 2.0));

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

(Observação: você pode compilá-lo e executá-lo diretamente do CodePad: http://codepad.org/UOgEqAMA )

Resultado:

fmodf (-10,2, 2,0) = -0,20 == FALHA!

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

P i
fonte
Infelizmente, isso não funciona com inteiros. Eles precisam ser convertidos em ponto flutuante antes da divisão para permitir seu uso floor(). Além disso, você pode perder a precisão ao converter para float: Tente (float)1000000001/3, você ficará surpreso com os resultados!
cmaster - restabelecer monica
9

Acabei de notar que Bjarne Stroustrup rotula %como o operador restante , não o operador módulo.

Eu apostaria que este é seu nome formal nas especificações ANSI C e C ++, e que o abuso de terminologia se insinuou. Alguém sabe disso?

Mas se for esse o caso, a função fmodf () do C (e provavelmente outras) são muito enganosas. eles devem ser rotulados como fremf (), etc

P i
fonte
1
A norma C11 (ou o rascunho público final para ser mais exato) menciona "módulo" seis vezes, mas apenas em relação à representação de vários tipos. Nem uma vez menciona "módulo" em relação ao operador de resto ( %).
Nisse Engström
7

A função geral mais simples para encontrar o módulo positivo seria esta- Funcionaria em valores positivos e negativos de x.

int modulo(int x,int N){
    return (x % N + N) %N;
}
Udayraj Deshmukh
fonte
6

Para inteiros, isso é simples. Apenas faça

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

onde estou supondo que Né positivo e representável no tipo de x. Seu compilador favorito deve ser capaz de otimizar isso, de modo que termine em apenas uma operação de mod no assembler.

Jens Gustedt
fonte
3
Não funciona: int x=-9001; unsigned int N=2000;pois dá 2295, não 999.
Hubert Kario
1
@HubertKario Talvez verifique novamente? Não há nenhuma maneira de algo módulo 2000 dar 2295, você deve ter cometido um erro.
sam hocevar
2
@SamHocevar: Acho que o problema aqui são as estranhas regras de promoção de inteiros em C. assinado promover para não assinado e promover um valor inteiro com sinal negativo para não assinado invoca o comportamento indefinido em C.
datenwolf
1
Eu acredito que uma forma muito mais simples (e mais eficiente) seria: (x < 0) ? (x % N + N) : (x % N).
Chris Nolet
3

A melhor solução ¹para um matemático é usar Python.

A sobrecarga de operadores C ++ tem pouco a ver com isso. Você não pode sobrecarregar operadores para tipos integrados. O que você deseja é simplesmente uma função. É claro que você pode usar modelos C ++ para implementar essa função para todos os tipos relevantes com apenas 1 pedaço de código.

A biblioteca C padrão fornece fmod, se bem me lembro o nome, para tipos de ponto flutuante.

Para inteiros, você pode definir um modelo de função C ++ que sempre retorna um resto não negativo (correspondente à divisão 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);
}

... e apenas escreva em mod(a, b)vez de a%b.

Aqui, o tipo Integerprecisa ser um tipo inteiro assinado.

Se você quiser o comportamento matemático comum em que o sinal do resto é igual ao sinal do divisor, você pode fazer, por exemplo,

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

… Com a mesma restrição Integer, que é um tipo assinado.


¹ Porque a divisão inteira do Python gira em direção ao infinito negativo.

Saúde e hth. - Alf
fonte
seu código parece ter o mesmo bug que o meu tinha antes da minha edição. E se b for negativo? :)
Armen Tsirunyan
1
@Armen: obrigado! mas estou com preguiça de editar apenas por isso ... :-)
Saúde e hth. - Alf
@ArmenTsirunyan: o rresultado deve tornar a= r + b*(a/b)verdadeiro. não importa como a divisão inteira é implementada, o b*somethingé um múltiplo de b. isso torna rum resultado de módulo válido, mesmo se negativo. você pode adicionar abs ( b) a ele e ainda será um resultado de módulo válido.
Saúde e hth. - Alf
2
@downvoters: Esta resposta ainda está correta, enquanto a "solução" selecionada agora contém comentários incorretos devido a novas garantias em C ++ 11. É muito irônico rejeitar uma resposta que ainda está correta. Sem nenhuma razão dada, deve-se supor que pelo menos 2 pessoas associativas, com grau quase absoluto de ignorância, leram o comentário dessa questão e votaram negativamente por associação automática. Por favor, explique seus votos negativos.
Saúde e hth. - Alf
1
O resultado matematicamente desejado é que o resto seja zero ou tenha o mesmo sinal do divisor (denominador). Se o divisor for negativo, o resto deve ser zero ou negativo. A implementação C / C ++ resulta no resto sendo zero ou tendo o mesmo sinal do dividendo (numerador).
rcgldr
2

Oh, eu odeio% design para isso também ...

Você pode converter dividendos em não assinados da seguinte forma:

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

result = (offset + dividend) % divider

onde o deslocamento é o mais próximo de (-INT_MIN) múltiplo do módulo, portanto, adicionar e subtrair não alterará o módulo. Observe que ele tem tipo sem sinal e o resultado será inteiro. Infelizmente, ele não pode converter corretamente os valores INT_MIN ... (- offset-1), pois eles causam estouro arifmético. Mas esse método tem a vantagem de apenas uma aritmética adicional por operação (e nenhuma condição) ao trabalhar com divisor constante, portanto, pode ser usado em aplicativos do tipo DSP.

Há um caso especial, onde o divisor é 2 N (potência inteira de dois), para o qual o módulo pode ser calculado usando aritmética simples e lógica bit a bit como

dividend&(divider-1)

por exemplo

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

A maneira mais comum e menos complicada é obter o módulo usando esta função (funciona apenas com divisor positivo):

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

Este resultado apenas corrige se for negativo.

Além disso, você pode enganar:

(p% q + q)% q

É muito curto, mas usa dois% -s, que normalmente são lentos.

Vovanium
fonte
2

Acredito que outra solução para esse problema seria usar variáveis ​​do tipo long em vez de int.

Eu estava trabalhando em um código em que o operador% estava retornando um valor negativo que causou alguns problemas (para gerar variáveis ​​aleatórias uniformes em [0,1] você realmente não quer números negativos :)), mas depois de mudar as variáveis ​​para digite long, tudo estava funcionando perfeitamente e os resultados correspondiam aos que eu estava obtendo ao executar o mesmo código em python (importante para mim, pois eu queria ser capaz de gerar os mesmos números "aleatórios" em várias plataformas.

david
fonte
2

Aqui está uma nova resposta a uma pergunta antiga, com base neste documento de pesquisa da Microsoft e nas referências nele contidas.

Observe que de C11 e C ++ 11 em diante, a semântica de divtornou-se truncada para zero (consulte Recursos[expr.mul]/4 ). Além disso, para Ddividido por d, C ++ 11 garante o seguinte sobre o quociente qTe o restorT

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

onde signummapeia para -1, 0, +1, dependendo se seu argumento é <, ==,> do que 0 (veja este Q&A para o código-fonte).

Com a divisão truncada, o sinal do resto é igual ao sinal do dividendoD , ou seja -1 % 8 == -1. C ++ 11 também fornece uma std::divfunção que retorna uma estrutura com membros quoterem acordo com a divisão truncada.

Existem outras definições possíveis, por exemplo, a chamada divisão de piso pode ser definida em termos da divisão truncada embutida

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

Com a divisão com piso, o sinal do resto é igual ao sinal do divisord . Em linguagens como Haskell e Oberon, existem operadores embutidos para divisão por piso. Em C ++, você precisa escrever uma função usando as definições acima.

Ainda outra forma é a divisão euclidiana , que também pode ser definida em termos da divisão truncada embutida

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

Com a divisão euclidiana, o sinal do resto é sempre positivo .

TemplateRex
fonte
2

Para uma solução que não usa branches e apenas 1 mod, você pode fazer o seguinte

// Works for other sizes too,
// assuming you change 63 to the appropriate value
int64_t mod(int64_t x, int64_t div) {
  return (x % div) + (((x >> 63) ^ (div >> 63)) & div);
}
Kyle Butt
fonte
1
/ * Aviso: o macro mod avalia os efeitos colaterais de seus argumentos várias vezes. * /
# define mod (r, m) (((r)% (m)) + ((r) <0)? (m): 0)

... ou apenas se acostume a conseguir qualquer representante para a classe de equivalência.

Eric Towers
fonte
2
“Acostumar-se a conseguir algum representante para a aula de equivalência” ?! Isso não faz sentido. Se você quiser, pode usar o "representante" original r. O %operador não tem nada a ver com classes de equivalência. É o operador resto e o resto é bem definido algebricamente para ser não negativo e menor que o divisor. Infelizmente, C o definiu da maneira errada. Ainda assim, +1 por ter uma das melhores respostas.
R .. GitHub PARAR DE AJUDAR O ICE
0

Modelo de exemplo 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);
}

Com este modelo, o resto retornado será zero ou terá o mesmo sinal do divisor (denominador) (o equivalente a arredondar para o infinito negativo), em vez de o comportamento C ++ do resto ser zero ou ter o mesmo sinal do dividendo ( numerador) (o equivalente a arredondar para zero).

rcgldr
fonte
-1
define  MOD(a, b)       ((((a)%(b))+(b))%(b))
lkw
fonte
Isso funciona, mas defini-lo como uma macro como essa é horrível. Esta é uma versão
modelada
-1
unsigned mod(int a, unsigned b) {
    return (a >= 0 ? a % b : b - (-a) % b);
}
Neuer
fonte
-1

Esta solução (para uso quando modfor positiva) evita tomar operações de divisão negativa ou resto juntas:

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

Eu faria:

((-1)+8) % 8 

Isso adiciona o último número ao primeiro antes de fazer o módulo, dando 7 conforme desejado. Isso deve funcionar para qualquer número até -8. Para -9, adicione 2 * 8.

Toby O'Connell
fonte
2
E para uma variável cujo valor pode ser -99999?
Keith Thompson