C/C++ unsigned integer overflow
It means the value "wraps around".
UINT_MAX + 1 == 0
UINT_MAX + 2 == 1
UINT_MAX + 3 == 2
.. and so on
As the link says, this is like the modulo operator: http://en.wikipedia.org/wiki/Modulo_operation
Why is unsigned integer overflow defined behavior but signed integer overflow isn't?
The historical reason is that most C implementations (compilers) just used whatever overflow behaviour was easiest to implement with the integer representation it used. C implementations usually used the same representation used by the CPU - so the overflow behavior followed from the integer representation used by the CPU.
In practice, it is only the representations for signed values that may differ according to the implementation: one's complement, two's complement, sign-magnitude. For an unsigned type there is no reason for the standard to allow variation because there is only one obvious binary representation (the standard only allows binary representation).
Relevant quotes:
C99 6.2.6.1:3:
Values stored in unsigned bit-fields and objects of type unsigned char shall be represented using a pure binary notation.
C99 6.2.6.2:2:
If the sign bit is one, the value shall be modified in one of the following ways:
— the corresponding value with sign bit 0 is negated (sign and magnitude);
— the sign bit has the value −(2N) (two’s complement);
— the sign bit has the value −(2N − 1) (one’s complement).
Nowadays, all processors use two's complement representation, but signed arithmetic overflow remains undefined and compiler makers want it to remain undefined because they use this undefinedness to help with optimization. See for instance this blog post by Ian Lance Taylor or this complaint by Agner Fog, and the answers to his bug report.
c++ Integer overflow in spite of using unsigned int and modulo operations
Basically problem is you have integer overflow just after multiplication.
To overcome this problem you have to approach topic using one of two solutions.
- use integer type which can hold a result of such magnitude, for example:
unsigned long long int
- use algorithm which is able to do that calculation without integer overflow
(for that I can't find good and simple document in English)
Using second approach:
constexpr unsigned mutiplyModulo(unsigned a, unsigned b, unsigned n)
{
unsigned m = 1, w = 1;
while (m) {
if (b & m)
w = (w + a) % n;
a = (a << 1) % n;
m <<= 1;
}
return w;
}
constexpr unsigned int intpow(unsigned int x, unsigned int n)
{
unsigned int r = 1;
while (n) {
if (n & 1)
r *= x;
x *= x;
n /= 2;
}
return r;
}
unsigned int foo(unsigned int orders)
{
constexpr auto mod = intpow(10u, 9u) + 7u;
unsigned int total = mutiplyModulo(orders, orders + 1, mod);
total /= 2;
return total;
}
https://godbolt.org/z/ePW7WxcTe
Unsigned integer overflow in comparison expressions
From the C Standard (6.5.6 Additive operators)
4 If both operands have arithmetic type, the usual arithmetic
conversions are performed on them.
and (6.5.8 Relational operators)
3 If both of the operands have arithmetic type, the usual arithmetic
conversions are performed.
and at last (6.3.1.8 Usual arithmetic conversions)
- ... Otherwise, the integer promotions are performed on both operands.
and (6.3.1.1 Boolean, characters, and integers)
2 The following may be used in an expression wherever an int or
unsigned int may be used:
— An object or expression with an integer type (other than int or
unsigned int) whose integer conversion rank is less than or equal to
the rank of int and unsigned int.
— A bit-field of type _Bool, int, signed int, or unsigned int.
If an int can represent all values of the original type (as restricted
by the width, for a bit-field), the value is converted to an int;
otherwise, it is converted to an unsigned int. These are called the
integer promotions. 58) All other types are unchanged by the integer
promotions.
So in the condition of the if statement
if ((a + b) > max)
all operands are converted to the type int
according to the integer promotions. And an object of the type int
is able to store the value of the integer expression a + b
where each operand is in turn converted to the type int
.
In fact the above if statement you may imagine the following way
if ( ( ( int )a + ( int )b ) > ( int )max )
or like
if ( ( ( unsigned int )a + ( unsigned int )b ) > ( unsigned int )max )
depending on whether the type int
or unsigned int
can store the values of the type uint16_t
.
An overflow can occur if for example the size of the type int
or unsigned int
is the same as the size of the type uint16_t
.
Detecting if an unsigned integer overflow has occurred when adding two numbers
You could use
if((a + b) < a)
The point is that if a + b
is overflowing, the result will be trimmed and must be lower then a
.
Consider the case with hypothetical bound range of 0 -> 9 (overflows at 10):
b
can be 9 at the most. For any value a
such that a + b >= 10
, (a + 9) % 10 < a
.
For any values a
, b
such that a + b < 10
, since b
is not negative, a + b >= a
.
Integer overflow happening with unsigned variables
%ld
in printf
will interpret any number as a signed one. Every number can be read as both signed or unsigned. To print your unsigned long as unsigned you should pass %lu
to printf
.
The difference between an unsigned or a signed number is on which assembly instructions the compiler will choose to use when handling this variable. At assembly level there are sets of instructions designed to handle what should be a signed number and others sets of instructions to handle unsigned numbers (e.g. when you check the value of the variable through an if
statement if it was declared as signed the compiler will generate some instructions and if not the compiler will generate others). char c = -1
and unsigned char c = 255
are stored as exact same values in memory.
Overflowing of Unsigned Int
unsigned
numbers can't overflow, but instead wrap around using the properties of modulo.
For instance, when unsigned int
is 32 bits, the result would be: (a * b) mod 2^32
.
As CharlesBailey pointed out, 253473829*13482018273
may use signed multiplication before being converted, and so you should be explicit about unsigned
before the multiplication:
unsigned int someint = 253473829U * 13482018273U;
Related Topics
/Usr/Lib/Libstdc++.So.6: Version 'Glibcxx_3.4.15' Not Found
Functions With Const Arguments and Overloading
How to Deal With Mutexes in Movable Types in C++
Demote Boost::Function to a Plain Function Pointer
Why Doesn't C++ Support Functions Returning Arrays
C++: Constructor Initializer For Arrays
How to Code a Modulo (%) Operator in C/C++/Obj-C That Handles Negative Numbers
Comparing Iterators from Different Containers
Creating All Possible K Combinations of N Items in C++
How to Use a Member Variable as a Default Argument in C++
Why Is 'This' a Pointer and Not a Reference
Initialize a Const Array in a Class Initializer in C++
Throwing Exceptions from Constructors
C++, Variable Declaration in 'If' Expression
How to Declare a Templated Struct/Class as a Friend
Difference Between Static, Auto, Global and Local Variable in the Context of C and C++