4

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

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

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

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

产生输出

1

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

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

4

3 回答 3

6

clangwith -Wconversionenabled 清楚地指出了您的错误：

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);
    ~~~~~~ ^~~~~~~~~~~

wandbox 上的实时示例

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

4294967293 % 11等于1。

于 2017-04-08T11:49:53.210 回答
3

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

通常的算术转换是在操作数上执行的。

通常的算术转换由 6.3.1.8 定义。相关部分是：

否则，如果无符号整数类型的操作数的等级大于或等于另一个操作数类型的等级，则将有符号整数类型的操作数转换为无符号整数类型的操作数的类型。

所以在 中x % m，x首先将其转换为无符号整数。

为了避免这种行为，您可以使用x % (int)m，尽管如果m > INT_MAX. 如果你想支持m > INT_MAX和否定x，你将不得不使用稍微复杂的逻辑。

于 2017-04-08T13:59:37.383 回答
1

其他人的回答很好地解释了 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;
}
于 2017-04-08T15:29:39.773 回答