Встретился мне вдруг код, реализующий целочисленное (2's complement) деление со знаком, в котором INT_MIN / -1 == INT_MAX, INT_MIN % -1 == -1, причем не по ошибке, а совершенно намеренно, но без комментария, откуда взялся резон для такого решения. Никто не в курсе, где такое было?
Если модули INT_MIN и INT_MAX равны, то это какой-то неправильный (OK, нетрадиционный) код дополнения до двух. Обычно модули равны если представление целых со знаком одно из следующих: - код дополнения до 1 (все биты инвертируют для обращения знака, и для лулзов имеем +0 и -0) - бит знакак и модуль (возможны те же лулзы)
Мне кажется, что ты имеешь дело с UB, реализованное таким конкретным способом, т.к. -INT_MIN в честном коде дополнения до 2 не представим (не отличим от +INT_MIN).
Конечно, не равны. В дополнении до двух abs(INT_MIN) = INT_MAX+1.
Мне кажется, что ты имеешь дело с UB, реализованное таким конкретным способом
Это противоречие в терминах, поскольку в данном случае имеем очень даже defined behavior; вопрос лишь в причинах такого решения, в отличие от INT_MIN/-1 = INT_MIN.
В приведённом примере деление не может дать частное в том же типе int, ибо не лезет. Переполнение выражения целочисленного типа со знаком — UB по определению стандарта языка. Это что касается INT_MIN / -1 == INT_MAX.
С INT_MIN % -1 == -1 дело интересней. Остаток может быть и можно было посчитать честно, т.к. он лезет в int, но поскольку он типично является побочным продуктом вычисления частного от деления, то на практике тоже получается «ой». По хорошему, стандарту стоило прописать этот случай в явном виде. Но сразу это не было сделано (в оригиинальной версии стандарта от 99-го года этого нет).
Зато есть в ISO/IEC 9899:201x Committee Draft — April 12, 2011 N1570:
6 When integers are divided, the result of the / operator is the algebraic quotient with any fractional part discarded. 105) If the quotient a/b is representable, the expression (a/b)*b + a%b shall equal a; otherwise, the behavior of both a/b and a%b is undefined.
В определенном смысле это логично. INT_MIN/-1 непредставимо, и лучшим приближением будет INT_MAX. А остаток вычисляется вычитанием второго из первого: INT_MIN - INT_MAX*-1 = -1.
обычно арифметические операции возвращают не "лучшее представление" (т.е. насыщение), а truncation (т.е. младшие биты результата). с этой точки зрения должно быть INT_MIN / -1 == 0 (и то же самое с умножением INT_MIN * -1). правда не очень понятно с остатком -- truncation дает 0, а вывод через r = D - d*q дает INT_MIN.
Трудно сказать, я такого по жизни не встречал. В случае MIPS архитектура не определяет результат деления INT_MIN на -1. То есть на усмотрение разработчика. Реальные процессоры выдают результат INT_MIN. Что совсем нелогично, но факт.
Видимо, она, но я в DSP не специалист. Хотелось бы знать, действительно есть ли железный процессор, в котором так реализовано (ну и умножение аналогично).
Ну вот вроде ж плавающие числа подобным реализованы почти везде (IEEE стандарт, происходящий от Интела). А это может аналогичная реализация для fixed point. Хотя прям конкретного железа я конечно не знаю, да и область не моя.
понятно, что идеального варианта здесь нет. для объективного сравнения нужно выписать набор полезных свойств операций / и %, и посмотреть, какой вариант сохраняет "больше". например, forall x < 0, y < 0: x / y >= 0 forall x: x % -1 == 0 forall x: abs(x / -1) == abs(x) forall x: x / -1 == x * -1
Безусловно, веса могут быть разные. Последнее свойство говорит, что деление нужно согласовывать с умножением: если INT_MIN / -1 == INT_MAX, то и INT_MIN * -1 == INT_MAX.
![[identity profile]](https://www.dreamwidth.org/img/silk/identity/openid.png){kind=small}
![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png)
winterfish
no subject
Date: 2014-06-11 03:47 am (UTC)Если модули INT_MIN и INT_MAX равны, то это какой-то неправильный (OK, нетрадиционный) код дополнения до двух. Обычно модули равны если представление целых со знаком одно из следующих:
- код дополнения до 1 (все биты инвертируют для обращения знака, и для лулзов имеем +0 и -0)
- бит знакак и модуль (возможны те же лулзы)
Мне кажется, что ты имеешь дело с UB, реализованное таким конкретным способом, т.к. -INT_MIN в честном коде дополнения до 2 не представим (не отличим от +INT_MIN).
no subject
Date: 2014-06-11 04:06 am (UTC)Мне кажется, что ты имеешь дело с UB, реализованное таким конкретным способом
Это противоречие в терминах, поскольку в данном случае имеем очень даже defined behavior; вопрос лишь в причинах такого решения, в отличие от INT_MIN/-1 = INT_MIN.
no subject
Date: 2014-06-11 04:40 am (UTC)С INT_MIN % -1 == -1 дело интересней. Остаток может быть и можно было посчитать честно, т.к. он лезет в int, но поскольку он типично является побочным продуктом вычисления частного от деления, то на практике тоже получается «ой». По хорошему, стандарту стоило прописать этот случай в явном виде. Но сразу это не было сделано (в оригиинальной версии стандарта от 99-го года этого нет).
Зато есть в ISO/IEC 9899:201x Committee Draft — April 12, 2011 N1570:
6 When integers are divided, the result of the / operator is the algebraic quotient with any fractional part discarded. 105) If the quotient a/b is representable, the expression (a/b)*b + a%b shall equal a; otherwise, the behavior of both a/b and a%b is undefined.
no subject
Date: 2014-06-11 04:50 am (UTC)no subject
Date: 2014-06-11 04:54 am (UTC)no subject
Date: 2014-06-11 03:50 am (UTC)no subject
Date: 2014-06-11 04:06 am (UTC)no subject
Date: 2014-06-11 03:53 am (UTC)a == (a/b)*b + (a%b)?Для 16 бит, a = -32768, b = -1
-32768 == 32767*-1 + (-1).no subject
Date: 2014-06-11 04:08 am (UTC)no subject
Date: 2014-06-11 04:57 am (UTC)INT_MIN/-1 непредставимо, и лучшим приближением будет INT_MAX.
А остаток вычисляется вычитанием второго из первого: INT_MIN - INT_MAX*-1 = -1.
no subject
Date: 2014-06-11 05:40 am (UTC)no subject
Date: 2014-06-11 02:32 pm (UTC)no subject
Date: 2014-06-11 06:14 am (UTC)no subject
Date: 2014-06-11 06:24 am (UTC)no subject
Date: 2014-06-11 06:11 pm (UTC)no subject
Date: 2014-06-11 06:27 pm (UTC)no subject
Date: 2014-06-11 06:44 pm (UTC)no subject
Date: 2014-06-11 05:32 am (UTC)forall x < 0, y < 0: x / y >= 0
forall x: x % -1 == 0
forall x: abs(x / -1) == abs(x)
forall x: x / -1 == x * -1
no subject
Date: 2014-06-11 06:13 am (UTC)BTW, последние два свойства - это одно и то же.
no subject
Date: 2014-06-11 12:38 pm (UTC)no subject
Date: 2014-06-11 06:28 pm (UTC)