?

Log in

No account? Create an account

Целочисленное со знаком, вопрос к залу - Общество дровосеков Бердичева по изучению Мишны

Jun. 10th, 2014

08:29 pm - Целочисленное со знаком, вопрос к залу

Previous Entry Share Next Entry


Встретился мне вдруг код, реализующий целочисленное (2's complement) деление со знаком, в котором INT_MIN / -1 == INT_MAX, INT_MIN % -1 == -1, причем не по ошибке, а совершенно намеренно, но без комментария, откуда взялся резон для такого решения. Никто не в курсе, где такое было?

Comments:

[User Picture]
From:archaicos
Date:June 11th, 2014 03:47 am (UTC)
(Link)
Что-то как-то странно.

Если модули INT_MIN и INT_MAX равны, то это какой-то неправильный (OK, нетрадиционный) код дополнения до двух. Обычно модули равны если представление целых со знаком одно из следующих:
- код дополнения до 1 (все биты инвертируют для обращения знака, и для лулзов имеем +0 и -0)
- бит знакак и модуль (возможны те же лулзы)

Мне кажется, что ты имеешь дело с UB, реализованное таким конкретным способом, т.к. -INT_MIN в честном коде дополнения до 2 не представим (не отличим от +INT_MIN).
(Reply) (Thread)
[User Picture]
From:spamsink
Date:June 11th, 2014 04:06 am (UTC)
(Link)
Конечно, не равны. В дополнении до двух abs(INT_MIN) = INT_MAX+1.

Мне кажется, что ты имеешь дело с UB, реализованное таким конкретным способом

Это противоречие в терминах, поскольку в данном случае имеем очень даже defined behavior; вопрос лишь в причинах такого решения, в отличие от INT_MIN/-1 = INT_MIN.
(Reply) (Parent) (Thread)
[User Picture]
From:archaicos
Date:June 11th, 2014 04:40 am (UTC)
(Link)
В приведённом примере деление не может дать частное в том же типе 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.


Edited at 2014-06-11 04:42 am (UTC)
(Reply) (Parent) (Thread)
[User Picture]
From:spamsink
Date:June 11th, 2014 04:50 am (UTC)
(Link)
Я разве что-то сказал про какой-то язык или стандарт?
(Reply) (Parent) (Thread)
[User Picture]
From:archaicos
Date:June 11th, 2014 04:54 am (UTC)
(Link)
Тогда не используй INT_MIN, INT_MAX и п.р. чтобы не вводить в заблуждение лишний раз. :)
(Reply) (Parent) (Thread)
[User Picture]
From:panchul
Date:June 11th, 2014 03:50 am (UTC)
(Link)
Для 2's complement это просто неверно. Или как?
(Reply) (Thread)
[User Picture]
From:spamsink
Date:June 11th, 2014 04:06 am (UTC)
(Link)
Что значит "неверно"? INT_MIN/-1 == INT_MIN неясно, чем лучше.
(Reply) (Parent) (Thread)
[User Picture]
From:yatur
Date:June 11th, 2014 03:53 am (UTC)
(Link)
Может, они хотели, чтобы выполнялась формула

a == (a/b)*b + (a%b)?

Для 16 бит, a = -32768, b = -1
-32768 == 32767*-1 + (-1).
(Reply) (Thread)
[User Picture]
From:spamsink
Date:June 11th, 2014 04:08 am (UTC)
(Link)
Разумеется, но для -32768/-1 = -32768, и в остатке 0 она тоже будет выполняться.
(Reply) (Parent) (Thread)
[User Picture]
From:ramlamyammambam
Date:June 11th, 2014 04:57 am (UTC)
(Link)
В определенном смысле это логично.
INT_MIN/-1 непредставимо, и лучшим приближением будет INT_MAX.
А остаток вычисляется вычитанием второго из первого: INT_MIN - INT_MAX*-1 = -1.
(Reply) (Thread)
[User Picture]
From:some41
Date:June 11th, 2014 05:40 am (UTC)
(Link)
обычно арифметические операции возвращают не "лучшее представление" (т.е. насыщение), а truncation (т.е. младшие биты результата). с этой точки зрения должно быть INT_MIN / -1 == 0 (и то же самое с умножением INT_MIN * -1). правда не очень понятно с остатком -- truncation дает 0, а вывод через r = D - d*q дает INT_MIN.
(Reply) (Parent) (Thread)
[User Picture]
From:some41
Date:June 11th, 2014 02:32 pm (UTC)
(Link)
Ерунду написал. Truncation как раз даёт INT_MIN / -1 == INT_MIN.
(Reply) (Parent) (Thread)
[User Picture]
From:spamsink
Date:June 11th, 2014 06:14 am (UTC)
(Link)
Естественно. Меня удивляет, кому это вдруг могло понадобиться.
(Reply) (Parent) (Thread)
[User Picture]
From:ramlamyammambam
Date:June 11th, 2014 06:24 am (UTC)
(Link)
Трудно сказать, я такого по жизни не встречал. В случае MIPS архитектура не определяет результат деления INT_MIN на -1. То есть на усмотрение разработчика. Реальные процессоры выдают результат INT_MIN. Что совсем нелогично, но факт.
(Reply) (Parent) (Thread)
[User Picture]
From:sab123
Date:June 11th, 2014 06:11 pm (UTC)
(Link)
Это, видимо, арифметика "с насыщением", где INT_MIN и INT_MAX служат минус бесконечностью и плюс бесконечностью. Небось полезна в каком-нибудь DSP?
(Reply) (Parent) (Thread)
[User Picture]
From:spamsink
Date:June 11th, 2014 06:27 pm (UTC)
(Link)
Видимо, она, но я в DSP не специалист. Хотелось бы знать, действительно есть ли железный процессор, в котором так реализовано (ну и умножение аналогично).
(Reply) (Parent) (Thread)
[User Picture]
From:sab123
Date:June 11th, 2014 06:44 pm (UTC)
(Link)
Ну вот вроде ж плавающие числа подобным реализованы почти везде (IEEE стандарт, происходящий от Интела). А это может аналогичная реализация для fixed point. Хотя прям конкретного железа я конечно не знаю, да и область не моя.
(Reply) (Parent) (Thread)
[User Picture]
From:some41
Date:June 11th, 2014 05:32 am (UTC)
(Link)
понятно, что идеального варианта здесь нет. для объективного сравнения нужно выписать набор полезных свойств операций / и %, и посмотреть, какой вариант сохраняет "больше". например,
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
(Reply) (Thread)
[User Picture]
From:spamsink
Date:June 11th, 2014 06:13 am (UTC)
(Link)
Логично, но кроме простого подсчета им можно еще и разные веса придавать в зависимости от "нужности".

BTW, последние два свойства - это одно и то же.

(Reply) (Parent) (Thread)
[User Picture]
From:some41
Date:June 11th, 2014 12:38 pm (UTC)
(Link)
Безусловно, веса могут быть разные. Последнее свойство говорит, что деление нужно согласовывать с умножением: если INT_MIN / -1 == INT_MAX, то и INT_MIN * -1 == INT_MAX.

Edited at 2014-06-11 12:39 pm (UTC)
(Reply) (Parent) (Thread)
[User Picture]
From:spamsink
Date:June 11th, 2014 06:28 pm (UTC)
(Link)
Конечно, нужно согласовывать.
(Reply) (Parent) (Thread)