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

Question

РЕДАКТИРОВАТЬ Предупреждение общественного здравоохранения - этот вопрос содержит ложное предположение о неопределенном поведении.См. Принятый ответ.

После прочтения недавнего сообщения в блоге я много размышлял о целесообразности избегания всех неопределенных в стандартах допущений в коде C и 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, что также не определено стандартами.

Answer 1

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

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

Answer 2

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

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

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