음수로 모듈로 연산

음수로 모듈로 연산

---

ac 프로그램에서 나는 아래 작업을 시도하고 있었다 (동작을 확인하기 위해)

 x = 5 % (-3);
 y = (-5) % (3);
 z = (-5) % (-3); 

printf("%d ,%d ,%d", x, y, z); 

(2, -2 , -2)gcc에서 와 같이 출력을주었습니다 . 나는 매번 긍정적 인 결과를 기대하고있었습니다. 계수가 음수 일 수 있습니까? 아무도이 행동을 설명 할 수 있습니까?

---

C99 는 다음과 같이 표현할 수 있어야 합니다 a/b.

(a/b) * b + a%b 는 같을 것이다a

논리적으로 말이됩니다. 권리?

이것이 무엇으로 연결되는지 봅시다 :

---

예 A. 5/(-3)는-1

=> (-1) * (-3) + 5%(-3) =5

5%(-3)2 인 경우에만 발생할 수 있습니다 .

---

예 B. (-5)/3는-1

=> (-1) * 3 + (-5)%3 =-5

경우에만 발생할 수 (-5)%3있다-2

---

%C 의 연산자는 모듈로 연산자가 아니라 나머지 연산자입니다.

모듈로 및 나머지 연산자는 음수 값이 다릅니다.

나머지 연산자의 경우 결과의 부호는 피제수의 부호와 같으며 모듈로 연산자의 경우 결과의 부호는 제수와 같습니다.

C는 다음 과 같이 %작업을 정의합니다 a % b.

  a == (a / b * b) + a % b

를 /향해 정수 나누기를 사용 0합니다. 그것은 모듈로 연산자가 아닌 나머지 연산자로 0정의하는 (음의 무한대가 아닌)쪽으로 수행되는 잘림입니다 %.

---

C99 사양을 기반으로 : a == (a / b) * b + a % b

계산할 함수를 작성할 수 있습니다 (a % b) == a - (a / b) * b!

int remainder(int a, int b)
{
    return a - (a / b) * b;
}

모듈로 연산의 경우 다음과 같은 기능을 가질 수 있습니다 (가정 b > 0)

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

내 결론은 a % bC에서 나머지 연산이며 모듈로 연산 이 아니라는 것 입니다.

---

나는 숫자가 음수인지 확인할 필요가 없다고 생각합니다.

포지티브 모듈로를 찾는 간단한 함수는 다음과 같습니다.

편집 : 가정 N > 0및N + N - 1 <= INT_MAX

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

이것은 x의 양수 값 과 음수 값 모두에 적용 됩니다 .

원래 추신 : 또한 @chux가 가리키는 아웃으로, 귀하의 x와 N은 대체 각각 INT_MAX-1 및 INT_MAX 같은 도달 할 수있는 경우 int에 long long int.

그리고 그들이 오랫동안 긴 한계 (예 : LLONG_MAX 근처)를 넘으면 여기에 다른 답변에 설명 된대로 양수와 음수를 별도로 처리해야합니다.

---

다른 답변은 C99 이상 에서 설명 했으므로 음의 피연산자가 포함 된 정수의 나누기는 항상 0으로 잘립니다 .

C89에서 , 결과가 상향 또는 하향으로 반올림되는지는 구현-정의 됨에 유의한다 . 모든 표준에서 (a/b) * b + a%b동일 하기 때문에 음의 피연산자가 포함 a된 결과 %도 C89에 구현 정의되어 있습니다.

---

계수가 음수 일 수 있습니까?

%Euclidean_division 이후 가 아니라 나머지 연산자 인 나머지 나눗셈이므로 음수 일 수 있습니다 . C99이므로 결과는 0, 음수 또는 양수일 수 있습니다.

 // a % b
 7 %  3 -->  1  
 7 % -3 -->  1  
-7 %  3 --> -1  
-7 % -3 --> -1  

모듈로 원 영업 이익은 고전적인 유클리드 모듈로 하지 %.

나는 매번 긍정적 인 결과를 기대하고있었습니다.

때마다 잘 정의 된 유클리드 모듈로 수행하려면 a/b정의를, a,b어떤 부호이며, 결과는 부정적인 결코 :

int modulo_Euclidean(int a, int b) {
  int m = a % b;
  if (m < 0) {
    // m += (b < 0) ? -b : b; // avoid this form: it is UB when b == INT_MIN
    m = (b < 0) ? m - b : m + b;
  }
  return m;
}

modulo_Euclidean( 7,  3) -->  1  
modulo_Euclidean( 7, -3) -->  1  
modulo_Euclidean(-7,  3) -->  2  
modulo_Euclidean(-7, -3) -->  2   

---

The result of Modulo operation depends on the sign of numerator, and thus you're getting -2 for y and z

Here's the reference

http://www.chemie.fu-berlin.de/chemnet/use/info/libc/libc_14.html

Integer Division

This section describes functions for performing integer division. These functions are redundant in the GNU C library, since in GNU C the '/' operator always rounds towards zero. But in other C implementations, '/' may round differently with negative arguments. div and ldiv are useful because they specify how to round the quotient: towards zero. The remainder has the same sign as the numerator.

---

In Mathematics, where these conventions stem from, there is no assertion that modulo arithmetic should yield a positive result.

Eg.

1 mod 5 = 1, but it can also equal -4. That is, 1/5 yields a remainder 1 from 0 or -4 from 5. (Both factors of 5)

Similarly, -1 mod 5 = -1, but it can also equal 4. That is, -1/5 yields a remainder -1 from 0 or 4 from -5. (Both factors of 5)

For further reading look into equivalence classes in Mathematics.

---

Modulus operator gives the remainder. Modulus operator in c usually takes the sign of the numerator

1. x = 5 % (-3) - here numerator is positive hence it results in 2
2. y = (-5) % (3) - here numerator is negative hence it results -2
3. z = (-5) % (-3) - here numerator is negative hence it results -2

Also modulus(remainder) operator can only be used with integer type and cannot be used with floating point.

---

According to C99 standard, section 6.5.5 Multiplicative operators, the following is required:

(a / b) * b + a % b = a

Conclusion

The sign of the result of a remainder operation, according to C99, is the same as the dividend's one.

Let's see some examples (dividend / divisor):

When only dividend is negative

(-3 / 2) * 2  +  -3 % 2 = -3

(-3 / 2) * 2 = -2

(-3 % 2) must be -1

When only divisor is negative

(3 / -2) * -2  +  3 % -2 = 3

(3 / -2) * -2 = 2

(3 % -2) must be 1

When both divisor and dividend are negative

(-3 / -2) * -2  +  -3 % -2 = -3

(-3 / -2) * -2 = -2

(-3 % -2) must be -1

---

6.5.5 Multiplicative operators

Syntax

1. multiplicative-expression:
   • cast-expression
   • multiplicative-expression * cast-expression
   • multiplicative-expression / cast-expression
   • multiplicative-expression % cast-expression

Constraints

2. Each of the operands shall have arithmetic type. The operands of the % operator shall have integer type.

Semantics

3. The usual arithmetic conversions are performed on the operands.

4. The result of the binary * operator is the product of the operands.

5. The result of the / operator is the quotient from the division of the first operand by the second; the result of the % operator is the remainder. In both operations, if the value of the second operand is zero, the behavior is undefined.

6. When integers are divided, the result of the / operator is the algebraic quotient with any fractional part discarded [1]. If the quotient a/b is representable, the expression (a/b)*b + a%b shall equal a.

[1]: This is often called "truncation toward zero".

---

I believe it's more useful to think of mod as it's defined in abstract arithmetic; not as an operation, but as a whole different class of arithmetic, with different elements, and different operators. That means addition in mod 3 is not the same as the "normal" addition; that is; integer addition.

So when you do:

5 % -3

You are trying to map the integer 5 to an element in the set of mod -3. These are the elements of mod -3:

{ 0, -2, -1 }

So:

0 => 0, 1 => -2, 2 => -1, 3 => 0, 4 => -2, 5 => -1

Say you have to stay up for some reason 30 hours, how many hours will you have left of that day? 30 mod -24.

But what C implements is not mod, it's a remainder. Anyway, the point is that it does make sense to return negatives.

---

The modulo operator is just like the mod operator when the number is positive, but different if the number is negative.

Many a times in the problems we are asked to give the answer modulo 10^9+7.

Let the answer(before using modulo) be denoted by 'a'.

Simple Straightforward Rule-

if a is positive, then a modulo 10^9+7= a%(10^9+7)

if a is negative, then a modulo 10^9+7= (a%(10^9+7))+(10^9+7)

If, in such problems, we find that any step of the loop may calculate a value that is out of the integer range (if we are using integers), then we can use the modulo operator in that step itself. The final answer will be as if we have used the modulo operator only once.

This is because- (a*b)%c=((a%c)(b%c))%c Same goes for addition and subtraction.

참고URL : https://stackoverflow.com/questions/11720656/modulo-operation-with-negative-numbers