Как сделать двойное добавление без неопределенного поведения?

ИЗМЕНИТЬ Предупреждение об общественном здравоохранении. Этот вопрос содержит ложное предположение о неопределенном поведении. Смотрите принятый ответ.

Прочитав недавнюю запись в блоге, я много думал о практичности отказа от всех стандартов. -неопределенные предположения в коде C и C++. Вот фрагмент, вырезанный из С++, чтобы сделать беззнаковое 128-битное добавление...

void c_UInt64_Pair::operator+= (const c_UInt64_Pair &p)
{
  m_Low  += p.m_Low;
  m_High += p.m_High;

  if (m_Low < p.m_Low)  m_High++;
}

Это явно зависит от предположений о поведении переполнения. Очевидно, что большинство машин могут поддерживать двоичное целое число правильного типа (хотя, возможно, построение из 32-битных фрагментов или чего-то еще), но, по-видимому, растет вероятность того, что оптимизатор может использовать здесь стандартное неопределенное поведение. То есть единственный способ, которым может быть выполнено условие m_Low < p.m_Low, — это переполнение m_Low += p.m_Low, что является неопределенным поведением, поэтому оптимизатор может на законных основаниях решить, что условие всегда не выполняется. В этом случае этот код просто сломан.

Поэтому вопрос...

Как вы можете написать достаточно эффективную версию вышеизложенного, не полагаясь на неопределенное поведение?

Предположим, что у вас есть подходящее 64-битное двоичное машинное число, но у вас есть вредоносный компилятор, который всегда будет интерпретировать ваше неопределенное поведение наихудшим из возможных (или невозможных) способов. Кроме того, предположим, что у вас нет какой-то специальной встроенной, встроенной библиотеки или чего-то еще, что могло бы сделать это за вас.

ИЗМЕНИТЬ небольшое уточнение. Речь идет не только об обнаружении переполнения, но и о том, что и m_Low, и m_High в конечном итоге дают правильные результаты по модулю 2^64, что также не определено стандартами.


person Steve314    schedule 25.08.2010    source источник
comment
1/ Это не C. Почему вы помечаете этот вопрос тегом C? 2/Если бы это был C и, возможно, даже C++, это не зависело бы от неопределенного поведения: переполнения целочисленных типов без знака определены и имеют поведение по модулю: 6.2.5.9 в стандарте C99.   -  person Pascal Cuoq    schedule 25.08.2010
comment
@Pascal: На самом деле, см. раздел 5.4 самого последнего черновика (здесь у меня нет стандарта С++ 03, но я считаю, что поведение не изменилось). Если во время вычисления выражения результат не математически определено или не находится в диапазоне представляемых значений для своего типа, поведение не определено.   -  person Billy ONeal    schedule 25.08.2010
comment
@Pascal - (1) вопрос в равной степени касается C и C++. Предоставление примера только в одном не означает, что вопрос касается только этого. (2) Когда это произошло? Если это правда, это ответ (возможно, С++ еще не импортировал соответствующее правило C, но если нет, то, несомненно, будет), поэтому поместите его в ответ со ссылкой, и я приму.   -  person Steve314    schedule 25.08.2010
comment
Хорошо, это была немного рефлекторная реакция после того, как я увидел много вопросов по C/C++. Для таких тонких вопросов, как эти, их просто нельзя рассматривать как один и тот же язык. Пожалуйста, помните о моем замечании только о том, что в C99 этот код будет определяться частью.   -  person Pascal Cuoq    schedule 25.08.2010
comment
@ Steve314: И ты знаешь, что это в равной степени касается и того, и другого? В данном конкретном случае я считаю, что да. В других случаях это не так. Предположим, вы должны были спросить о типе 'a', например: разные ответы в C и C++.   -  person David Thornley    schedule 25.08.2010
comment
@ Дэвид - я знаю, потому что мне нужен ответ для обоих, независимо от того, одинаков ли он для обоих. C и C++ достаточно тесно связаны, поэтому сравнение и противопоставление важны для людей, которые используют оба. Я действительно использую только C++, правда, но мне все еще интересно, как он сравнивается с C.   -  person Steve314    schedule 26.08.2010
comment
Могу ли я поставить +1 тому, кто добавил предупреждение?   -  person R.. GitHub STOP HELPING ICE    schedule 26.08.2010


Ответы (2)


Из стандарта C++ 1998, 3.9.1(4): «Целые числа без знака, объявленные беззнаковыми, должны подчиняться законам арифметики по модулю 2^n, где n — количество битов в представлении значения этого конкретного размера целого числа». Обратите внимание, что «целое число» здесь относится к любому целочисленному типу, а не только к int.

Следовательно, если предположить, что это целые числа без знака, как предполагает «UInt64» в типе, это определенное поведение в C++ и должно работать должным образом.

person David Thornley    schedule 25.08.2010
comment
Что такое стандарт С++ 1995? Я знаю о 99-м, 03-м... никогда о таком не слышал. В любом случае, хотя это и так, это не означает, что определено поведение переполнения, см. раздел, который я цитировал выше. Если во время вычисления выражения результат не определен математически или находится вне диапазона представляемых значений для его тип, поведение не определено. - person Billy ONeal; 25.08.2010
comment
@Billy, поскольку беззнаковые типы следуют правилам арифметики по модулю, никогда не будет результата, выходящего за пределы диапазона представляемых значений, поэтому поведение определено. Сноска к 3.9.1/4 говорит об этом. - person Rob Kennedy; 25.08.2010
comment
@Rob: Ах .. сноска поясняет это. Я бы сказал, однако, что отрывок, который он процитировал, не делает это очевидным по своей сути. - person Billy ONeal; 26.08.2010
comment
@Billy ONeal: Предположим, что цитата верна для C++. В любом случае то же правило по модулю применимо к C99. Арифметика по модулю 2^n всегда четко определена, нет никакой двусмысленности в отношении результатов: они всегда находятся в диапазоне 0 <= x < 2^n. Таким образом, дополнительный пункт о математически неопределенном поведении никогда не может применяться к беззнаковым типам. Целочисленные типы без знака переносятся, но не переполняются. - person Jens Gustedt; 26.08.2010
comment
@Billy: Изменено на 1998 год. Насколько я знаю, никогда не существовало стандарта 1999 года, то есть C. У меня нет под рукой версии 2003 года, и я не планирую ее приобретать. Кроме того, указание того, что unsigned подчиняется законам модульной арифметики, определяет поведение, а переполнение четко определено в модульной арифметике. - person David Thornley; 26.08.2010
comment
Вы также можете сослаться на стандарт C. - person R.. GitHub STOP HELPING ICE; 26.08.2010
comment
Какой был бы самый удобный портативный способ получить младшие 32 бита произведения двух произвольных 32-битных чисел, произведение которых может превышать 2 ^ 63? Если unsigned int имеет размер 32 бита или меньше, или если signed int имеет размер 65 бит или больше, проблем не будет, но что, если оба они 64-битные? UInt32 преобразуются в Int64, после чего продукт дает неопределенные результаты. Приведение операнда к UInt64 может сработать, но это, вероятно, добавит значительный дополнительный код для процессоров, где в противном случае 'int' был бы 32-битным. - person supercat; 21.03.2011

Если вам нужен действительно эффективный метод, вам придется писать код на чем-то другом, кроме C или C++. Для разумной эффективности вы должны гарантировать, что переполнение никогда не произойдет, а также обнаружить и компенсировать, когда оно могло бы произойти.

По сути, для каждого 64-битного компонента нужно отдельно вычислять сложения, используя младшие 63 бита и старшие биты. Из этих отдельных вычислений вы можете определить, сколько было 64-битных файлов и был ли перенос.

Затем, когда вы делаете верхнее 64-битное добавление, вы добавляете перенос, если он есть. Если в результате этого возникает перенос, то вы переполнили свою 128-битную переменную, и вам нужно вызвать исключение или иным образом обработать случай.

person swestrup    schedule 25.08.2010
comment
Неа; то, что вы говорите, верно для целочисленных типов со знаком, но не для беззнаковых. - person David Thornley; 25.08.2010
comment
И... почему вы не сможете эффективно сделать это на C или C++? Какую альтернативу вы бы предложили более эффективно? - person Billy ONeal; 25.08.2010
comment
Наиболее эффективно было бы использовать аппаратные средства, предназначенные именно для этой цели, будь то 128-битные регистры или флаги переноса. - person swestrup; 26.08.2010
comment
Но я исправлен в отношении всего подписанного/неподписанного. Мне почему-то вспомнилось, что все арифметические переполнения не определены. - person swestrup; 26.08.2010
comment
@swestrup - меня тоже обманули :-( - person Steve314; 26.08.2010
comment
@David - это звучит педантично (для целочисленных типов со знаком), но не практически (в том смысле, что вы можете использовать целочисленные типы без знака для выполнения арифметических действий со знаком). Однако это вполне может сломаться для чего угодно, кроме сложения/вычитания. - person Steve314; 26.08.2010