Modulo operation with negative numbers

Question

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?

Answer 1

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.

Answer 2

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

Answer 3

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.

Answer 4

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

int mod(int m, float n)
{  
  return m - floor(m/n)*n;
}

Answer 5

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.

Answer 6

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.

Answer 7

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.

Answer 8

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   

Answer 9

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

Answer 10

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.

Answer 11

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.

Answer 12

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

Answer 13

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.

Answer 14

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.