295

In a C program I was trying the below operations (Just to check the behavior)

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

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

It gave me output as (2, -2 , -2) in gcc. I was expecting a positive result every time. Can a modulus be negative? Can anybody explain this behavior?

5

14 Answers 14

238

C99 requires that when a/b is representable:

(a/b) * b + a%b shall equal a

This makes sense, logically. Right?

Let's see what this leads to:


Example A. 5/(-3) is -1

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

This can only happen if 5%(-3) is 2.


Example B. (-5)/3 is -1

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

This can only happen if (-5)%3 is -2

8
  • 1
    Should the compiler be smart enough and detect that an unsigned modulo another unsigned is always positive? Currently (well, GCC 5.2) the compiler seems to think that "%" returns an "int" in this case, rather than "unsigned" even when both operands are uint32_t or bigger. Commented Sep 24, 2016 at 14:56
  • @FrederickNord Do you have an example to show that behavior?
    – chux
    Commented Feb 24, 2017 at 16:16
  • 18
    Understand that what you describe is the usual int(a/b) (truncate) description of mod. But it is also possible that the rule is floor(a/b) (Knuth). In the Knuth case -5/3 is -2 and the mod becomes 1. In short: one module has a sign that follows the dividend sign (truncate), the other module has a sign that follows the divisor sign (Knuth).
    – user8017719
    Commented May 27, 2018 at 9:36
  • 4
    This is a case of the C standard being exactly not what I want. I have never wanted truncate to zero or negative modulo numbers, but often want the opposite and need to work around C.
    – Joe
    Commented Aug 6, 2018 at 22:27
  • 1
    @Nick the a/b in the expression (a/b) * b + a%b above is integer division, so (a/b) * b is not equal to a unless a is divisible by b. Commented Dec 17, 2021 at 17:51
235

The % operator in C is not the modulo operator but the remainder operator.

Modulo and remainder operators differ with respect to negative values.

With a remainder operator, the sign of the result is the same as the sign of the dividend (numerator) while with a modulo operator the sign of the result is the same as the divisor (denominator).

C defines the % operation for a % b as:

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

with / the integer division with truncation towards 0. That's the truncation that is done towards 0 (and not towards negative inifinity) that defines the % as a remainder operator rather than a modulo operator.

4
  • 22
    Remainder is the result of modulo operation by definition. There should be no such thing as remainder operator because there is no such thing as remainder operation, it's called modulo.
    – gronostaj
    Commented Jun 27, 2015 at 20:49
  • 85
    @gronostaj not in CS. Look at higher level languages like Haskell or Scheme that both define two different operators (remainder and modulo in Scheme, rem and mod in Haskell). These operators specifications differ on these languages on how the division is done: truncation towards 0 or toward negative infinity. By the way the C Standard never calls the % the modulo operator, they just name it the % operator.
    – ouah
    Commented Dec 21, 2015 at 16:55
  • 4
    Not to be confused with the remainder function in C, which implements IEEE remainder with round-towards-nearest semantics in the division
    – Eric
    Commented Sep 18, 2017 at 2:11
  • @gronostaj The link that you provided specifically makes the distinction between least positive remainder, and least absolute remainder which is obviously not always positive. It gives -2 as the least absolute remainder of 43 / 5 (since 43 = 9 * 5 - 2). The CS definition is yet again different. But it is worth pointing out that just because we learned something when we were 10 years old, there still might be some subtleties. Try round(2.5) in Python, for instance. It's 2, not 3. And that is mathematically correct, to prevent bias in statistical moments. Commented Feb 18, 2021 at 17:25
97

Based on the C99 Specification: a == (a / b) * b + a % b

We can write a function to calculate (a % b) == a - (a / b) * b!

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

For modulo operation, we can have the following function (assuming b > 0)

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

My conclusion is that a % b in C is a remainder operation and NOT a modulo operation.

2
  • 5
    This does not give positive results when b is negative (and in fact for r and b both negative it gives results less than -b). To ensure positive results for all inputs you could use r + abs(b) or to match bs sign you could change the condition to r*b < 0 instead. Commented Sep 20, 2016 at 11:42
  • 2
    @MartinEnder r + abs(b) is UB when b == INT_MIN.
    – chux
    Commented Sep 27, 2018 at 4:20
88

I don't think there isn't any need to check if the number is negative.

A simple function to find the positive modulo would be this -

Edit: Assuming N > 0 and N + N - 1 <= INT_MAX

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

This will work for both positive and negative values of x.

Original P.S: also as pointed out by @chux, If your x and N may reach something like INT_MAX-1 and INT_MAX respectively, just replace int with long long int.

And If they are crossing limits of long long as well (i.e. near LLONG_MAX), then you shall handle positive and negative cases separately as described in other answers here.

2
  • 3
    Note that when N < 0, the result may be negative as in modulo(7, -3) --> -2. Also x % N + N can overflow int math which is undefined behavior. e.g. modulo(INT_MAX - 1,INT_MAX) might result in -3.
    – chux
    Commented Sep 27, 2018 at 4:17
  • Yes, in that case you may simply use long long int, or handle the negative case separately (at the cost of losing simplicity). Commented Oct 7, 2018 at 14:08
15

Can a modulus be negative?

% can be negative as it is the remainder operator, the remainder after division, not after Euclidean_division. Since C99 the result may be 0, negative or positive.

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

The modulo OP wanted is a classic Euclidean modulo, not %.

I was expecting a positive result every time.

To perform a Euclidean modulo that is well defined whenever a/b is defined, a,b are of any sign and the result is never negative:

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   
10

The other answers have explained in C99 or later, division of integers involving negative operands always truncate towards zero.

Note that, in C89, whether the result round upward or downward is implementation-defined. Because (a/b) * b + a%b equals a in all standards, the result of % involving negative operands is also implementation-defined in C89.

5

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

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

Semantics

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

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

  3. 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.

  4. 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".

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.

1
  • 5
    You are referring to a text about ANSI C. This is a fairly old norm of C. Not sure if the text is correct with regard to ANSI C, but definitely not with regard to C99. In C99 §6.5.5 integer division is defined to always truncate towards zero.
    – Palec
    Commented Feb 5, 2014 at 20:36
2

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.

2
  • 1
    Equivalence class is a different concept and modulo is defined in a very strict way. Let's say we have two integer numbers a and b, b <> 0. According to the Euclidean division theorem there exists exactly one pair of integers m, r where a = m * b + r and 0 <= r < abs( b ) . The said r is the result of the (mathematical) modulo operation and by definition is non negative. More reading and further links on Wikipedia: en.wikipedia.org/wiki/Euclidean_division
    – Ister
    Commented May 9, 2018 at 6:54
  • 1
    That isn't true. 1 mod 5 is always 1. -4 mod 5 might be 1 too, but they are different things.
    – FelipeC
    Commented Jun 5, 2019 at 7:35
1

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.

1
  • 2
    It would be nice if you can back this up with links to external resources.
    – J...S
    Commented Aug 26, 2017 at 16:13
1

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.

4
  • @FelipeC : if you're using the euclidean division approach, then whether you stayed up for 6 hours or 30 hours will still yield -18 (mod -24), which really provides you with no helpful information, since staying up for 6 versus 30 aren't remotely similar to each other. Commented Apr 3 at 17:19
  • @RAREKpopManifesto in both cases what remains of the day is 18 hours, so yes it provides helpful information.
    – FelipeC
    Commented Apr 4 at 10:28
  • that's a false equivalence cuz it involves asking a different question altogether - being up 30 hours mean the -18 refers to "how many hours you're short of 2 full days", while being up 6 hours mean -18 is "how many hours you're short of 1 full day". To be asking the same question of "how many hours you're short of 2 full days", the congruent value needs to be -42. The only congruence of your approach is "how many hours it's short of the next midnight after you went to bed" - a totally different question altogether. Commented Apr 8 at 4:26
  • @RAREKpopManifesto you misunderstand the abstract algebra. There is no 30 in integers modulo -24 (ℤ/-24ℤ). The members of this set are themselves a set, so the mathematical object we are talking about is {54, 30, 6, -18, -42}. 6 and 30 are not just equivalent, they are exactly the same mathematical object.
    – FelipeC
    Commented Apr 9 at 19:06
1

If N is the modulus (ie the divisor), then

(x + N) % N

will simply return the modulo of x.

In other words, as a function:

const modulo = (x, N) => (x + N) % N

Example:

result = modulo(-3, 12) // 9

0

I was looking for branchless euclidean modulo and this the closest I got:

#include <stdint.h>

int32_t moduloEuclidean(int32_t a, int32_t b)
{
    int32_t const int32_width = 32;
    int32_t const mod = a % b;

    // mod_sign_mask = (mod < 0)? 0b11111111... : 0
    int32_t const mod_sign_mask = mod >> (int32_width - 1);
    // abs_sign_mask = (b < 0)? 0b11111111... : 0
    int32_t const abs_sign_mask = b >> (int32_width - 1);
    // abs_value = (b < 0)? (~b - (-1)) : (b - 0)
    int32_t const abs_value = (abs_sign_mask ^ b) - abs_sign_mask;

    // result = a % b + (a % b < 0? abs(b) : 0)
    return mod + (mod_sign_mask & abs_value);
}

Note that this solution relies on 2's complement arithmetic and will work only on those platforms that support it. I recommend either compiling with -std=c23 or above or with -fwrapv flag supported by both gcc and clang.

There was a concern that moduloEuclidean(x, 0) has undefined behavior, however so does euclidean division.

6
  • Oh, you are right. It's weird it's UB even when we have standardized 2's complement. But even if it wasn't it would still yield incorrect sign value.
    – WENDYN
    Commented Mar 8 at 16:04
  • @chux-reinstate-monica, would (0 < (x)) - (x < (0)) work?
    – WENDYN
    Commented Mar 8 at 16:05
  • 1
    Ok, I realized it's an overflow when b is INT_MIN and it gets multiply by -1 which also it kinda messes with the result.
    – WENDYN
    Commented Mar 8 at 17:44
  • Okay, I switched to my own abs calculation that's not UB under 2's complement and masked it out when remainder is positive.
    – WENDYN
    Commented Mar 9 at 13:54
  • 1
    Minor: in addition to "solution relies on 2's complement ", it also relies on int is 32-bit. C spec has a minimum range implying at least 16-bit.
    – chux
    Commented Mar 9 at 14:08
-2

It seems the problem is that / is not floor operation.

int mod(int m, float n)
{  
  return m - floor(m/n)*n;
}
1
  • m converts to float before the division and subtraction and large values incur a precision loss. The division itself readily incurs a precision loss. return fmod(m, n) might be a reasonable alternative, yet using floating point for an integer problem is usually best avoided.
    – chux
    Commented Mar 6 at 16:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.