I looked into this [stackoverflow question relating to Big Integer][1] and specifically I do not understand this line (the words in italics):

&gt; In the BigInteger class, *I have no limits* and there are some helpful
&gt; functions there but it is pretty depressing to convert your beautiful
&gt; code to work with the BigInteger class, specially when primitive
&gt; operators don&#39;t work there and you must use functions from this class.

I don&#39;t know what I am missing but to represent something that has no limit you would require infinite memory ? Whats is the trick here ?

[1]:https://stackoverflow.com/questions/2776400/biginteger-or-not-biginteger

What does BigInteger having no limit mean?

I had been studying the algorithm for finding lonely integers in an array, and here is the implementation:

	int arr[] = {10, 20, 30, 5, 20, 10, 30};
    int LonelyInteger = 0;
    for(int i=0; i&lt; 7; i++)
    {
        LonelyInteger = LonelyInteger ^ arr[i];
    }

The result is `5`.

My question is - supposedly the integers (getting generated by the `XOR` operation) are **too large** due to this operation:

    LonelyInteger ^ arr[i]

Which leads to a potentially large integer which cannot be represented by the datatype say `int` in this case. My questions are:

1. Is it even possible that `XOR` will generate such a large integer value that cannot be stored in the `int` type?
2. If it is not possible that this can happen then is there a proof for this?


Can XOR of two integers go out of bounds?

How does Java handle integer underflows and overflows?

Leading on from that, how would you check/test that this is occurring?

How does Java handle integer underflows and overflows and how would you check for it?

-2147483648 is the smallest integer for integer type with 32 bits, but it seems that it will overflow in the `if(...)` sentence:

    if (-2147483648 &gt; 0)
        std::cout &lt;&lt; &quot;true&quot;;
    else
        std::cout &lt;&lt; &quot;false&quot;;

This will print `true` in my testing. However, if we cast -2147483648 to integer, the result will be different:

    if (int(-2147483648) &gt; 0)
        std::cout &lt;&lt; &quot;true&quot;;
    else
        std::cout &lt;&lt; &quot;false&quot;;

This will print `false`.

I&#39;m confused. Can anyone give an explanation on this?


----------


Update 02-05-2012:

Thanks for your comments, in my compiler, the size of int is 4 bytes. I&#39;m using VC for some simple testing. I&#39;ve changed the description in my question.

That&#39;s a lot of very good replys in this post, [AndreyT][1] gave a very detailed explanation on how the compiler will behave on such input, and how this minimum integer was implemented. [qPCR4vir][2] on the other hand gave some related &quot;curiosities&quot; and how integers are represented. So impressive!


  [1]: https://stackoverflow.com/a/14695202/2040924
  [2]: https://stackoverflow.com/a/14695400/2040924

(-2147483648&gt; 0) returns true in C++?

Unsigned integer overflow is well defined by both the C and C++ standards.  For example, the [C99 standard][1] (`&#167;6.2.5/9`) states 

&gt; A computation involving unsigned operands can never overﬂow,
because a result that cannot be represented by the resulting unsigned integer type is
reduced modulo the number that is one greater than the largest value that can be
represented by the resulting type.

However, both standards state that signed integer overflow is undefined behavior.  Again, from the C99 standard (`&#167;3.4.3/1`)

&gt; An example of undeﬁned behavior is the behavior on integer overﬂow

Is there an historical or (even better!) a technical reason for this discrepancy?


  [1]: http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1570.pdf

Why is unsigned integer overflow defined behavior but signed integer overflow isn&#39;t?

I am trying to get the sum of `1 + 2 + ... + 1000000000`, but I&#39;m getting funny results in PHP and [Node.js][1].

**PHP**

    $sum = 0;
    for($i = 0; $i &lt;= 1000000000 ; $i++) {
        $sum += $i;
    }
    printf(&quot;%s&quot;, number_format($sum, 0, &quot;&quot;, &quot;&quot;));   // 500000000067108992

**Node.js**

    var sum = 0;
    for (i = 0; i &lt;= 1000000000; i++) {
        sum += i ;
    }
    console.log(sum); // 500000000067109000

The correct answer can be calculated using

    1 + 2 + ... + n = n(n+1)/2

Correct answer = **500000000500000000**, so I decided to try another language.

**GO**

    var sum , i int64
    for i = 0 ; i &lt;= 1000000000; i++ {
        sum += i
    }
    fmt.Println(sum) // 500000000500000000

But it works fine! So what is wrong with my PHP and Node.js code?

Perhaps this a problem of interpreted languages, and that&#39;s why it works in a compiled language like Go? If so, would other interpreted languages such as Python and Perl have the same problem?

  [1]: http://en.wikipedia.org/wiki/Node.js
  [2]: http://en.wikipedia.org/wiki/Python_%28programming_language%29
  [3]: http://en.wikipedia.org/wiki/Perl


Unexpected results when working with very big integers on interpreted languages

I need to compute an expression which looks like:
`A*B - C*D`, where their types are: `signed long long int A, B, C, D;`
Each number can be really big (not overflowing its type). While `A*B` could cause overflow, at same time expression `A*B - C*D` can be really small. How can I compute it correctly?

For example: `MAX * MAX - (MAX - 1) * (MAX + 1) == 1`, where `MAX = LLONG_MAX - n` and n - some natural number.

How to avoid overflow in expr. A * B - C * D

I was writing a program in C++ to find all solutions of *a*&lt;sup&gt;*b*&lt;/sup&gt; = *c*, where *a*, *b* and *c* together use all the digits 0-9 exactly once. The program looped over values of *a* and *b*, and it ran a digit-counting routine each time on *a*, *b* and *a&lt;sup&gt;b&lt;/sup&gt;* to check if the digits condition was satisfied.

However, spurious solutions can be generated when *a*&lt;sup&gt;*b*&lt;/sup&gt; overflows the integer limit. I ended up checking for this using code like:

    unsigned long b, c, c_test;
    ...
    c_test=c*b;         // Possible overflow
    if (c_test/b != c) {/* There has been an overflow*/}
    else c=c_test;      // No overflow

Is there a better way of testing for overflow? I know that some chips have an internal flag that is set when overflow occurs, but I&#39;ve never seen it accessed through C or C++.

---

Beware that ***signed* `int` overflow is undefined behaviour in C and C++**, and thus you have to detect it without actually causing it. For signed int overflow before addition, see *https://stackoverflow.com/questions/3944505/detecting-signed-overflow-in-c-c*.


How do I detect unsigned integer overflow?

```
long long int n = 2000*2000*2000*2000;    // overflow

long long int n = pow(2000,4);            // works
long long int n = 16000000000000;         // works
```

Why does the first one overflow (multiplying integer literal constants to assign to a long long)?

What&#39;s different about it vs. the second or third ones?

Why does long long n = 2000*2000*2000*2000; overflow?

The following block of codes gives the output as 0.

    public class HelloWorld{

        public static void main(String []args){
            int product = 1;
		    for (int i = 10; i &lt;= 99; i++) {
		    	product *= i;
		    }
		    System.out.println(product);
        }
    }

Please can somebody explain why this happens?


Why does Java think that the product of all numbers from 10 to 99 is 0?

I want to handle the special case where multiplying two numbers together causes an overflow. The code looks something like this:

    int a = 20;
    long b = 30;
    
    // if a or b are big enough, this result will silently overflow
    long c = a * b;

That&#39;s a simplified version. In the real program `a` and `b` are sourced elsewhere at runtime. What I want to achieve is something like this:

    long c;
    if (a * b will overflow) {
        c = Long.MAX_VALUE;
    } else {
        c = a * b;
    }

How do you suggest I best code this?

Update: `a` and `b` are always non-negative in my scenario.


How can I check if multiplying two numbers in Java will cause an overflow?

Adding two 32-bit integers can result an integer overflow:

    uint64_t u64_z = u32_x + u32_y;

This overflow can be avoided if one of the 32-bit integers is first casted or added to a 64-bit integer.

    uint64_t u64_z = u32_x + u64_a + u32_y;

However, if the compiler decides to reorder the addition:

    uint64_t u64_z = u32_x + u32_y + u64_a;

the integer overflow might still happen.

Are compilers allowed to do such a reordering or can we trust them to notice the result inconsistency and keep the expression order as is?


(A + B + C) ≠ (A + C + B​) and compiler reordering

I want to define a function that takes an `unsigned int` as argument and returns an `int` congruent modulo UINT_MAX+1 to the argument.

A first attempt might look like this:

    int unsigned_to_signed(unsigned n)
    {
        return static_cast&lt;int&gt;(n);
    }

But as any language lawyer knows, casting from unsigned to signed for values larger than INT_MAX is implementation-defined.

I want to implement this such that (a) it only relies on behavior mandated by the spec; and (b) it compiles into a no-op on any modern machine and optimizing compiler.

As for bizarre machines...  If there is no signed int congruent modulo UINT_MAX+1 to the unsigned int, let&#39;s say I want to throw an exception.  If there is more than one (I am not sure this is possible), let&#39;s say I want the largest one.

OK, second attempt:

    int unsigned_to_signed(unsigned n)
    {
        int int_n = static_cast&lt;int&gt;(n);

        if (n == static_cast&lt;unsigned&gt;(int_n))
            return int_n;

        // else do something long and complicated
    }

I do not much care about the efficiency when I am not on a typical twos-complement system, since in my humble opinion that is unlikely.  And if my code becomes a bottleneck on the omnipresent sign-magnitude systems of 2050, well, I bet someone can figure that out and optimize it then.

Now, this second attempt is pretty close to what I want.  Although the cast to `int` is implementation-defined for some inputs, the cast back to `unsigned` is guaranteed by the standard to preserve the value modulo UINT_MAX+1.  So the conditional does check exactly what I want, and it will compile into nothing on any system I am likely to encounter.

However...  I am still casting to `int` without first checking whether it will invoke implementation-defined behavior.  On some hypothetical system in 2050 it could do who-knows-what.  So let&#39;s say I want to avoid that.

Question:  What should my &quot;third attempt&quot; look like?

To recap, I want to:

 - Cast from unsigned int to signed int
 - Preserve the value mod UINT_MAX+1
 - Invoke only standard-mandated behavior
 - Compile into a no-op on a typical twos-complement machine with optimizing compiler

[Update]

Let me give an example to show why this is not a trivial question.

Consider a hypothetical C++ implementation with the following properties:

 - `sizeof(int)` equals 4
 - `sizeof(unsigned)` equals 4
 - `INT_MAX` equals 32767
 - `INT_MIN` equals -2&lt;sup&gt;32&lt;/sup&gt; + 32768
 - `UINT_MAX` equals 2&lt;sup&gt;32&lt;/sup&gt; - 1
 -  Arithmetic on `int` is modulo 2&lt;sup&gt;32&lt;/sup&gt; (into the range `INT_MIN` through `INT_MAX`)
 - `std::numeric_limits&lt;int&gt;::is_modulo` is true
 - Casting unsigned `n` to int preserves the value for 0 &lt;= n &lt;= 32767 and yields _zero_ otherwise

On this hypothetical implementation, there is exactly one `int` value congruent (mod UINT_MAX+1) to each `unsigned` value.  So my question would be well-defined.

I claim that this hypothetical C++ implementation fully conforms to the C++98, C++03, and C++11 specifications.  I admit I have not memorized every word of all of them...  But I believe I have read the relevant sections carefully.  So if you want me to accept your answer, you either must (a) cite a spec that rules out this hypothetical implementation or (b) handle it correctly.

Indeed, a correct answer must handle _every_ hypothetical implementation permitted by the standard. That is what &quot;invoke only standard-mandated behavior&quot; means, by definition.

Incidentally, note that `std::numeric_limits&lt;int&gt;::is_modulo` is utterly useless here for multiple reasons.  For one thing, it can be `true` even if unsigned-to-signed casts do not work for large unsigned values.  For another, it can be `true` even on one&#39;s-complement or sign-magnitude systems, if arithmetic is simply modulo the entire integer range.  And so on.  If your answer depends on `is_modulo`, it&#39;s wrong.

[Update 2]

[hvd&#39;s answer][1] taught me something:  My hypothetical C++ implementation for integers is _not_ permitted by modern C.  The C99 and C11 standards are very specific about the representation of signed integers; indeed, they only permit twos-complement, ones-complement, and sign-magnitude (section 6.2.6.2 paragraph (2); ).

But C++ is not C.  As it turns out, this fact lies at the very heart of my question.

The original C++98 standard was based on the much older C89, which says (section 3.1.2.5):

&gt; For each of the signed integer types, there is a corresponding (but
&gt; different) unsigned integer type (designated with the keyword
&gt; unsigned)  that uses the same amount of storage (including sign
&gt; information) and has the same alignment requirements.  The range of
&gt; nonnegative values of a signed integer type is a subrange of the
&gt; corresponding unsigned integer type, and the representation of the
&gt; same value in each type is the same.

C89 says nothing about only having one sign bit or only allowing twos-complement/ones-complement/sign-magnitude.

The C++98 standard adopted this language nearly verbatim (section 3.9.1 paragraph (3)):

&gt; For each of the signed integer types, there exists a corresponding
&gt; (but different) *unsigned integer type*: &quot;`unsigned char`&quot;, &quot;`unsigned
&gt; short int`&quot;, &quot;`unsigned int`&quot;, and &quot;`unsigned long int`&quot;, each of
&gt; which occupies the same amount of storage and has the same alignment
&gt; requirements (3.9) as the corresponding signed integer type ; that
&gt; is, each *signed integer* type has the same object representation as
&gt; its corresponding *unsigned integer* type. The range of nonnegative
&gt; values of a signed integer type is a subrange of the corresponding
&gt; unsigned integer type, and the value representation of each
&gt; corresponding signed/unsigned type shall be the same.

The C++03 standard uses essentially identical language, as does C++11.

No standard C++ spec constrains its signed integer representations to any C spec, as far as I can tell.  And there is nothing mandating a single sign bit or anything of the kind.  All it says is that _non-negative_ signed integers must be a subrange of the corresponding unsigned.

So, again I claim that INT_MAX=32767 with INT_MIN=-2&lt;sup&gt;32&lt;/sup&gt;+32768 is permitted.  If your answer assumes otherwise, it is incorrect unless you cite a **C++** standard proving me wrong.

  [1]: https://stackoverflow.com/a/13208789/768469

Efficient unsigned-to-signed cast avoiding implementation-defined behavior

At first glance, this question may seem like a duplicate of https://stackoverflow.com/questions/199333/best-way-to-detect-integer-overflow-in-c-c, however it is actually significantly different.

I&#39;ve found that while detecting an unsigned integer overflow is pretty trivial, detecting a *signed* overflow in C/C++ is actually more difficult than most people think.

The most obvious, yet naive, way to do it would be something like:

    int add(int lhs, int rhs)
    {
     int sum = lhs + rhs;
     if ((lhs &gt;= 0 &amp;&amp; sum &lt; rhs) || (lhs &lt; 0 &amp;&amp; sum &gt; rhs)) {
      /* an overflow has occurred */
      abort();
     }
     return sum; 
    }

The problem with this is that according to the C standard, signed integer overflow is *undefined behavior.*  In other words, according to the standard, as soon as you even cause a signed overflow, your program is just as invalid as if you dereferenced a null pointer.  So you can&#39;t cause undefined behavior, and then try to detect the overflow after the fact, as in the above post-condition check example.

Even though the above check is likely to work on many compilers, you can&#39;t count on it.  In fact, because the C standard says signed integer overflow is undefined, some compilers (like GCC) will [optimize away the above check][1] when optimization flags are set, because the compiler assumes a signed overflow is impossible.  This totally breaks the attempt to check for overflow.

So, another possible way to check for overflow would be:

    int add(int lhs, int rhs)
    {
     if (lhs &gt;= 0 &amp;&amp; rhs &gt;= 0) {
      if (INT_MAX - lhs &lt;= rhs) {
       /* overflow has occurred */
       abort();
      }
     }
     else if (lhs &lt; 0 &amp;&amp; rhs &lt; 0) {
      if (lhs &lt;= INT_MIN - rhs) {
       /* overflow has occurred */
       abort();
      }
     }
     
     return lhs + rhs;
    }

This seems more promising, since we don&#39;t actually add the two integers together until we make sure in advance that performing such an add will not result in overflow.  Thus, we don&#39;t cause any undefined behavior.  

However, this solution is unfortunately a lot less efficient than the initial solution, since you have to perform a subtract operation just to test if your addition operation will work.  And even if you don&#39;t care about this (small) performance hit, I&#39;m still not entirely convinced this solution is adequate.  The expression `lhs &lt;= INT_MIN - rhs` seems exactly like the sort of expression the compiler might optimize away, thinking that signed overflow is impossible.  

So is there a better solution here?  Something that is guaranteed to 1) not cause undefined behavior, and 2) not provide the compiler with an opportunity to optimize away overflow checks?  I was thinking there might be some way to do it by casting both operands to unsigned, and performing checks by rolling your own two&#39;s-complement arithmetic, but I&#39;m not really sure how to do that.

  [1]: http://patrakov.blogspot.com/2008_10_01_archive.html

Detecting signed overflow in C/C++

I&#39;ve found that `java.lang.Integer` implementation of `compareTo` method looks as follows:

    public int compareTo(Integer anotherInteger) {
        int thisVal = this.value;
        int anotherVal = anotherInteger.value;
        return (thisVal&lt;anotherVal ? -1 : (thisVal==anotherVal ? 0 : 1));
    }

The question is why use comparison instead of subtraction:

    return thisVal - anotherVal;

Java Integer compareTo() - why use comparison vs. subtraction?

As we know, [signed integer overflow is undefined behavior](https://stackoverflow.com/questions/4240748/allowing-signed-integer-overflows-in-c-c). But there is something interesting in C++11 `cstdint` documentation:

&gt; signed integer type with width of exactly 8, 16, 32 and 64 bits respectively with no padding bits and **using 2&#39;s complement for negative values** (provided only if the implementation directly supports the type)

&lt;sub&gt;[See link](http://en.cppreference.com/w/cpp/types/integer)&lt;/sub&gt;

And here is my question: since the standard says explicitly that for `int8_t`, `int16_t`, `int32_t` and `int64_t` negative numbers are 2&#39;s complement, is still overflow of these types an undefined behavior?

**Edit** I checked C++11 and C11 Standards and here is what I found:

C++11, &#167;18.4.1:
&gt; The header defines all functions, types, and macros the same as 7.20 in the C standard.

C11, &#167;7.20.1.1:
&gt;  The typedef name `intN_t` designates a signed integer type with width N, no padding bits, and a two’s complement representation. Thus, `int8_t` denotes such a signed integer type with a width of exactly 8 bits.

Is signed integer overflow still undefined behavior in C++?

This is an example to illustrate my question which involves some much more complicated code that I can&#39;t post here.

    #include &lt;stdio.h&gt;
    int main()
    {
        int a = 0;
        for (int i = 0; i &lt; 3; i++)
        {
            printf(&quot;Hello\n&quot;);
            a = a + 1000000000;
        }
    }

This program contains undefined behavior on my platform because `a` will overflow on the 3rd loop.

Does that make the **whole program** have undefined behavior, or only after the **overflow actually happens**? Could the compiler potentially work out that `a` **will** overflow so it can declare the whole loop undefined and not bother to run the printfs even though they all happen before the overflow?

&lt;sub&gt;(Tagged C and C++ even though are different because I&#39;d be interested in answers for both languages if they are different.)&lt;/sub&gt;


At what point in the loop does integer overflow become undefined behavior?

I have come across the below C++ program ([source][1]):

    #include &lt;iostream&gt;
    int main()
    {
        for (int i = 0; i &lt; 300; i++)
            std::cout &lt;&lt; i &lt;&lt; &quot; &quot; &lt;&lt; i * 12345678 &lt;&lt; std::endl;
    }

It looks like a simple program and gives the correct output on my local machine i.e. something like:

    0 0
    1 12345678
    2 24691356
    ...
    297 -628300930
    298 -615955252
    299 -603609574
    
But, on online IDEs like [codechef][2], it gives the following output:

    0 0
    1 12345678
    2 24691356
    ...
    4167 -95167326
    4168 -82821648
    4169 -7047597

Why doesn&#39;t the `for` loop terminate at 300? Also this program always terminates on `4169`. Why `4169` and not some other value?

  [1]: https://ideone.com/7F88MV
  [2]: https://www.codechef.com/ide

Program behaving strangely on online IDEs

I am looking for an efficient (optionally standard, elegant and easy to implement) solution to multiply relatively large numbers, and store the result into one or several integers :

Let say I have two 64 bits integers declared like this :

    uint64_t a = xxx, b = yyy; 

When I do `a * b`, how can I detect if the operation results in an overflow and in this case store the carry somewhere?

Please note that *I don&#39;t want to use any large-number library* since I have constraints on the way I store the numbers.

Catch and compute overflow during multiplication of two large integers

I often see questions relating to `Overflow` errors with [tag:VBA].

My question is why use the `integer` variable declaration instead of just defining all numerical variables (excluding `double` etc.) as `long`?

Unless you&#39;re performing an operation like in a for loop where you can guarantee that the value won&#39;t exceed the 32,767 limit, is there an impact on performance or something else that would dictate not using `long`?

Why Use Integer Instead of Long?

If, say, a 32-bit integer is overflowing, instead of upgrading `int` to `long`, can we make use of some 40-bit type if we need a range only within 2&lt;sup&gt;40&lt;/sup&gt;, so that we save 24 (64-40) bits for every integer?

If so, how?

I have to deal with billions and space is a bigger constraint.

If a 32-bit integer overflows, can we use a 40-bit structure instead of a 64-bit long one?

I am implementing a database application and I will use both JavaDB and MySQL as database. I have an ID column in my tables that has integer as type and I use the databases auto_increment-function for the value.

But what happens when I get more than 2 (or 4) billion posts and integer is not enough? Is the integer overflowed and continues or is an exception thrown that I can handle?

Yes, I could change to long as datatype, but how do I check when that is needed? And I think there is problem with getting the last_inserted_id()-functions if I use long as datatype for the ID-column.

What happens when auto_increment on integer column reaches the max_value in databases?

I was wandering in SO and saw [this question](https://stackoverflow.com/questions/18547114/why-do-we-need-argc-while-there-is-always-a-null-at-the-end-of-argv). Then I started wondering if I can overflow argc.

Standard says that `argv[argc]` must be a null pointer but this will be false if argc overflow.

(I [wrote](https://gist.github.com/boramalper/b0c6116ada4dd8f7e80a) a small C program and a python script to test it but got a `MemoryError`.)

Thanks!

----

&gt;### [Rationale for International Standard — Programming Languages — C](http://www.open-std.org/jtc1/sc22/wg14/www/C99RationaleV5.10.pdf) &#167;5.1.2.2.1 *Program startup*
&gt;The specification of `argc` and `argv` as arguments to `main` recognizes extensive prior practice. `argv[argc]` is required to be a null pointer to provide a redundant check for the end of the list, also on the basis of common practice. 


Can argc overflow?

Why doesn&#39;t this code print same number? : 

    long long a, b;
    a = 2147483647 + 1;
    b = 2147483648;
    printf(&quot;%lld\n&quot;, a);
    printf(&quot;%lld\n&quot;, b);

I know that int variable&#39;s maximum number is 2147483647 because int variable is 4 byte.
But as I know, long long variable is 8 byte, but why does that code act like that?

why does long long 2147483647 + 1 = -2147483648?

I noticed some unexpected behavior (unexpected relative to my personal expectations), and I&#39;m wondering if something if there is a bug in the JVM or if perhaps this is a fringe case where I don&#39;t understand some of the details of what exactly is supposed to happen.  Suppose we had the following code in a main method by itself:

    int i;
    int count = 0;
    for(i=0; i &lt; Integer.MAX_VALUE; i+=2){
      count++;
    }
    System.out.println(i++);

A naive expectation would be that this would print `Integer.MAX_VALUE-1`, the largest even representable `int`.  However, I believe integer arithmetic is supposed to &quot;rollover&quot; in Java, so adding 1 to `Integer.MAX_VALUE` should result in `Integer.MIN_VALUE`.  Since `Integer.MIN_VALUE` is still less than `Integer.MAX_VALUE`, the loop would keep iterating through the negative even ints.  Eventually it would get back to 0, and this process should repeat as an infinite loop.

When I actually run this code, I get non-deterministic results.  The result that gets printed tends to be on the order of half a million, but the exact value varies.  So not only is the loop terminating when I believe it should be an infinite loop, but it seems to terminate randomly.  What&#39;s going on?

My guess is that this is either a bug in the JVM, or there is a lot of funky optimization going on that makes this expected behavior.  Which is it?

All Integer Overflow Solutions on Gang of Coders

Total of 25 Integer Overflow Solutions