signed int modulo unsigned int 产生无意义的结果

Question

我需要在 C 中执行一个真正的数学模。允许负数作为模参数对我来说很有意义，因为我的模计算会产生负的中间结果，必须将其放回最小残留系统.但是允许否定模块是没有意义的，因此我写了

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

但是用负数和正模调用这样的函数

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

产生输出

我不明白为什么。能解释一下吗？

编辑：我知道运算符 % 与数学模不同，我知道它是如何为正数和负数定义的。我问的是不同的符号会做什么，而不是不同的符号。

Answer 1

clang 启用 -Wconversion 清楚地指出了你的错误：

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

转换为unsigned int时，-3变为4294967293。

4294967293 % 11 等于 1.

Answer 2

参见 C11 6.5.5（乘法运算符）/3:

The usual arithmetic conversions are performed on the operands.

usual arithmetic conversions 由 6.3.1.8 定义。相关部分是：

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.

所以在x % m中，首先将x转换为unsigned int。

要避免此行为，您可以使用 x % (int)m，但如果 m > INT_MAX 会出现故障。如果你想支持 m > INT_MAX 和否定 x，你将不得不使用稍微复杂的逻辑。

Answer 3

其他答案很好地解释了 OP 在 % 操作未产生预期结果之前将负值转换为 unsigned 时遇到了麻烦。

以下是解决方案：一种是求助于更广泛的数学（可能并不总是可用）。第二个是精心构造的，以避免任何未定义的行为（UB）、实现定义的（ID）行为或仅使用 int, unsigned 数学的溢出。它不依赖于 2 的补码。

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

试车手

#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 产生无意义的结果

signed int modulo unsigned int produces nonsense results

c

modulo

signedness

mod