Знак int по модулю unsigned int дает бессмысленные результаты

Question

Мне нужно выполнить настоящий математический модуль по Си. Для меня имеет смысл разрешить отрицательные числа для спланированного аргумента, поскольку мои модульные вычисления могут давать отрицательные промежуточные результаты, которые должны быть возвращены в систему наименьших вычетов. Но нет смысла разрешать отрицательный модуль, поэтому я написал

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

И я не понимаю почему. Не могли бы вы объяснить?

РЕДАКТИРОВАТЬ: Я знаю, что оператор% отличается от математического по модулю, и я знаю, как он определяется для положительных и отрицательных чисел. Я спрашивал, что это будет делать для другой подписи, а не для другой подписи.

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

живой пример на wandbox

---

Когда преобразовано в unsigned int, -3 становится 4294967293,

4294967293 % 11 равно 1,

Answer 2

См. C11 6.5.5 (Мультипликативные операторы) /3:

Обычные арифметические преобразования выполняются над операндами.

Обычные арифметические преобразования определены в 6.3.1.8. Соответствующая часть:

В противном случае, если операнд с целым типом без знака имеет ранг, больший или равный рангу типа другого операнда, тогда операнд с целым типом со знаком преобразуется в тип операнда с целым типом без знака.

Так в x % m, x сначала преобразуется в без знака Int.

Чтобы избежать такого поведения, вы можете использовать x % (int)m, хотя это будет работать со сбоями, если m > INT_MAX, Если вы хотите поддержать m > INT_MAX а также отрицательный xВам придется использовать немного более сложную логику.

Answer 3

Другие ответы хорошо объясняют, что у ОП были проблемы с преобразованием отрицательного значения в 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;
}