signed int modulo unsigned int produces nonsense results

Question

I need to perform a real mathematical modulo in C. It makes sense for me to allow negative numbers for the moduled argument, since my modular calculations can produce negative intermediate results, which must be put back into the least residue system. But it makes no sense to allow negative module, therefore i wrote

unsigned int mod( int x, unsigned int m )
{
    int r = x % m;
    return r >= 0 ? r : r + m;
}

However calling such function with negative number and positive module

printf("%u\n", mod(-3, 11));

produces output

And i don't understand why. Could you please explain?

EDIT: I know operator % is different from mathematical modulo and i know how it is defined for positive and negative numbers. I was asking what it will do for different signedness, not different sign.

It doesn't mean what you think it means, `x % m` first converts `x` to `unsigned int` so you have (probably) `0xfffffffdu % 11u` — harold, Apr 08 '17 at 11:48

Vittorio Romeo · Accepted Answer · 2017-04-08T16:31:52.073

7

clang with -Wconversion enabled clearly pinpoints your mistake:

prog.cc:3:15: warning: implicit conversion changes signedness: 'unsigned int' to 'int' [-Wsign-conversion]
    int r = x % m;
        ~   ~~^~~
prog.cc:3:13: warning: implicit conversion changes signedness: 'int' to 'unsigned int' [-Wsign-conversion]
    int r = x % m;
            ^ ~
prog.cc:4:21: warning: operand of ? changes signedness: 'int' to 'unsigned int' [-Wsign-conversion]
    return r >= 0 ? r : r + m;
    ~~~~~~          ^
prog.cc:4:25: warning: implicit conversion changes signedness: 'int' to 'unsigned int' [-Wsign-conversion]
    return r >= 0 ? r : r + m;
                        ^ ~
prog.cc:9:12: warning: implicit conversion changes signedness: 'unsigned int' to 'int' [-Wsign-conversion]
    return mod(-3, 11);
    ~~~~~~ ^~~~~~~~~~~

live example on wandbox

When converted to unsigned int, -3 becomes 4294967293.

4294967293 % 11 is equal to 1.

edited Apr 08 '17 at 16:31

answered Apr 08 '17 at 11:49

Vittorio Romeo

90,666
33
258
416

That's C++, OP uses C! (read the text, he spammed the C++ tag). – too honest for this site Apr 08 '17 at 13:25
@Olaf: that doesn't change my answer at all. The same warnings are reported with `clang` in C11 or C89 mode. – Vittorio Romeo Apr 08 '17 at 16:31
That is not the point. C and C++ are distinct languages. An answer should address the one ask about. Also aa specific implementation is a bad idea as a reference for questions about the language itself. The correct way would be using the corresponding sections of the standard to justify the behaviour. – too honest for this site Apr 08 '17 at 18:10

score 3 · Answer 2 · answered Apr 08 '17 at 13:59

See C11 6.5.5 (Multiplicative operators) /3:

The usual arithmetic conversions are performed on the operands.

The usual arithmetic conversions is defined by 6.3.1.8. The relevant part is:

Otherwise, if the operand that has unsigned integer type has rank greater or equal to the rank of the type of the other operand, then the operand with signed integer type is converted to the type of the operand with unsigned integer type.

So in x % m, the x is first converted to unsigned int.

To avoid this behaviour you could use x % (int)m,although this will malfunction if m > INT_MAX. If you want to support m > INT_MAX and also negative x, you'll have to use slightly more complicated logic.

chux - Reinstate Monica · Answer 3 · 2017-04-08T15:35:06.957

Others answers well explain OP had troubles as conversion of negative value to unsigned before the % operation did not yield expected results.

Below are solutions: one resorts to wider math (which may not always be available). The second is careful constructed to avoid any undefined behavior, (UB), implementation defined (ID) behavior or overflow using only int, unsigned math. It does not rely on 2's complement.

unsigned int mod_ref(int x, unsigned int m) {
  long long r = ((long long) x) % m;
  return (unsigned) (r >= 0 ? r : r + m);
}

unsigned int mod_c(int x, unsigned int m) {
  if (x >= 0) {
    return ((unsigned) x) % m;
  }
  unsigned negx_m1 = (unsigned) (-(x + 1));
  return m - 1 - negx_m1 % m;
}

A test driver

#include <limits.h>
#include <stdio.h>
#include <stdlib.h>

void testm(int x, unsigned int m) {
  if (m) {
    unsigned r0 = mod_ref(x, m);
    unsigned r1 = mod_c(x, m);
    if (r0 != r1) {
      printf("%11d %10u --> %10u %10u\n", x, m, r0, r1);
    }
  }
}

int main() {
  int ti[] = {INT_MIN, INT_MIN + 1, INT_MIN / 2, -2, -1, 0, 1, 2, INT_MAX / 2,
      INT_MAX - 1, INT_MAX};
  unsigned tu[] = {0, 1, 2, UINT_MAX / 2, UINT_MAX - 1, UINT_MAX};
  for (unsigned i = 0; i < sizeof ti / sizeof *ti; i++) {
    for (unsigned u = 0; u < sizeof tu / sizeof *tu; u++) {
      testm(ti[i], tu[u]);
    }
  }
  for (unsigned i = 0; i < 1000u * 1000; i++) {
    int x = rand() % 100000000;
    if (rand() & 1)
      x = -x - 1;
    unsigned m = (unsigned) rand();
    if (rand() & 1)
      m += INT_MAX + 1u;
    testm(x, m);
  }
  puts("done");
  return 0;
}

signed int modulo unsigned int produces nonsense results

3 Answers3

Linked