- 01
- 02
- 03
- 04
- 05
- 06
- 07
- 08
- 09
- 10
- 11
template <class T>
T checked_signed_add(T a, T b) {
if (a >= 0) {
if (b >= 0 && std::numeric_limits<T>::max() - a < b)
throw std::runtime_error("Integer overflow");
} else {
if (b < 0 && std::numeric_limits<T>::min() - a > b)
throw std::runtime_error("Integer overflow");
}
return a + b;
}
Follow us!
или какой тут был посыл, Борманд?
Я вот на шарю в этих ваших крестах, и потому этот пример выглядит для меня как очередной троллейбус.
Но вроде компиляторы, в отличие от стандарта, объявляют как undefined value, а не undefined behavior.
If during the evaluation of an expression, the result is not mathematically defined or not in the range of representable values for its type, the behavior is undefined.
Вообще говоря, у проца может быть железная проверка на overflow. И это сложение тупо вызовет прерывание и ось убьёт процесс нахуй, как и при делении на ноль... Поэтому тут и не undefined value, а именно behavior.
http://blog.llvm.org/2011/05/what-every-c-programmer-should-know.html
Signed integer overflow: If arithmetic on an 'int' type (for example) overflows, the result is undefined. One example is that "INT_MAX+1" is not guaranteed to be INT_MIN. This behavior enables certain classes of optimizations that are important for some code.
Both Clang and GCC accept the "-fwrapv" flag which forces the compiler to treat signed integer overflow as defined (other than divide of INT_MIN by -1).
http://blog.llvm.org/2011/05/what-every-c-programmer-should-know_21.html
2. Arithmetic that operates on undefined values is considered to produce a undefined value instead of producing undefined behavior. The distinction is that undefined values can't format your hard drive or produce other undesirable effects. A useful refinement happens in cases where the arithmetic would produce the same output bits given any possible instance of the undefined value. For example, the optimizer assumes that the result of "undef & 1" has zeros for its top bits, treating only the low bit as undefined. This means that ((undef & 1) >> 1) is defined to be 0 in LLVM, not undefined.
3. Arithmetic that dynamically executes an undefined operation (such as a signed integer overflow) generates a logical trap value which poisons any computation based on it, but that does not destroy your entire program. This means that logic downstream from the undefined operation may be affected, but that your entire program isn't destroyed. This is why the optimizer ends up deleting code that operates on uninitialized variables, for example.
Так-то можно вообще стандарт не читать, проверить на тестовом примере чтоб работало и ладно.
Вот именно! Поэтому не надо читать про поведение при UB и не надо тестировать поведение при UB. От этого нет никакой пользы, сплошной вред и ложные надежды. Нужно просто писать код так, чтобы в нём не было UB.
т.е. не на плюсах
-2 + (-3) = -5. Сумма меньше любого слагаемого. Переполнение, однако.
На основе Функции Борманда построить простой класс, хранящий unsigned int и использующий std::numeric_limits<unsigned int>::max() в качестве значения "NaN". Реализовать все нужные опереции и is_nan (переполнение и прочая питушня - NaN; каст NaN в unsigned int - exception). А желающие сами напишут себе знаковые инты и плавающих питунцов на основе BormandUnsigned.
(a+b)/2 ошибется при переполнении
a/2 + b/2 ошибется при a=1 и b=1
a + (b-a)/2 получится фигня если b < a
Vindicar'у понравится: есть ли хоть что-нибудь в этом языке что не было бы UB? ;)
так что можно замутить на макросах выяснение, какое представление используется для знаковых целых (т.к. компилятор уже всё знает)
49) A positional representation for integers that uses the binary digits 0 and 1, in which the values represented by successive bits are additive, begin
with 1, and are multiplied by successive integral power of 2, except perhaps for the bit with the highest position. (Adapted from the American National Dictionary for Information Processing Systems.)
Т.е. все эти 3 варианта они просто для примера привели. Сложно будет придумать какое-то новое представление. Но если вдруг придумаю - имею полное право юзать, стандарт разрешает.
пф, есть коды с двумя знаковыми битами
как раз чтобы +/- переполнение отслеживать
на x86 в качестве второго знакового бита можно использовать OF или как там его
SSDDDDDD DDDDDDDD DDDDDDDD DDDDDDDD
Тогда даже без OF можно переполнение поймать и обработать...
P.S. Ну т.е. в итоге всё-таки нельзя полагаться на то, что извращённая фантазия разрабов компилятора ограничена теми тремя представлениями...
Люр говорит о бинарном поиске, там инвариант a <= b. Я лично пишу в бинарном поиске a + (b - a) / 2.