Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C++ > integer or long overflow...

Reply
Thread Tools

integer or long overflow...

 
 
deancoo
Guest
Posts: n/a
 
      03-05-2005
When you increase the number contained within an integer or long data type
beyond its capacity, what happens? I've run into this situation, and it
continues right along. Is it simply just rolling over when it gets to its
limit? Curious.

d


 
Reply With Quote
 
 
 
 
Phil Staite
Guest
Posts: n/a
 
      03-05-2005
deancoo wrote:
> When you increase the number contained within an integer or long data type
> beyond its capacity, what happens? I've run into this situation, and it
> continues right along. Is it simply just rolling over when it gets to its
> limit? Curious.


I believe/suspect that like so many "edge effects" in C++ it is left
undefined. However, a 2's compliment architecture (as most C++
environments seem to be) will simply keep right on going - no
exception/trap as from say dedicated floating point hardware
experiencing a problem or say dividing by zero.

The gotcha with 2's compliment is that if you increase a signed integer
type (int or long) beyond it's limit, it becomes a very large negative
number and keeps "increasing" - becoming less negative, headed towards zero.
 
Reply With Quote
 
 
 
 
deancoo
Guest
Posts: n/a
 
      03-05-2005

"deancoo" <(E-Mail Removed)> wrote in message
news:Tl8Wd.2338$KI2.178@clgrps12...
> When you increase the number contained within an integer or long data type
> beyond its capacity, what happens? I've run into this situation, and it
> continues right along. Is it simply just rolling over when it gets to its
> limit? Curious.
>
> d


And how about emum types? Ultimately they're stored and compared as
numbers, but what is their size? Short?

d


 
Reply With Quote
 
deancoo
Guest
Posts: n/a
 
      03-05-2005
"Phil Staite" <(E-Mail Removed)> wrote in message
news:(E-Mail Removed)...
> deancoo wrote:
>> When you increase the number contained within an integer or long data
>> type beyond its capacity, what happens? I've run into this situation,
>> and it continues right along. Is it simply just rolling over when it
>> gets to its limit? Curious.

>
> I believe/suspect that like so many "edge effects" in C++ it is left
> undefined. However, a 2's compliment architecture (as most C++
> environments seem to be) will simply keep right on going - no
> exception/trap as from say dedicated floating point hardware experiencing
> a problem or say dividing by zero.
>
> The gotcha with 2's compliment is that if you increase a signed integer
> type (int or long) beyond it's limit, it becomes a very large negative
> number and keeps "increasing" - becoming less negative, headed towards
> zero.


Would anyone in their right mind overflow a data type and still use it?
Does it overflow consistently? I guess what I'm asking is, should I use it?
What other options exist if you need to generate a number larger than 2^32,
which is only used as a key for unique identification? I've already
confirmed that for my finite set of data, the overflowed data type maintains
uniqueness.

d


 
Reply With Quote
 
Prog37
Guest
Posts: n/a
 
      03-05-2005
deancoo wrote:

>
> Would anyone in their right mind overflow a data type and still use it?
> Does it overflow consistently? I guess what I'm asking is, should I use it?
> What other options exist if you need to generate a number larger than 2^32,
> which is only used as a key for unique identification? I've already
> confirmed that for my finite set of data, the overflowed data type maintains
> uniqueness.


Does your unique key fit in 32 bits or not?
Some c++ compilers gcc for instance offer the long long type.
On a 32 bit platform this will be a 64 bit integer.
The main drawback to using compiler extentions is the loss of portability.

Another option would be to define a c++ class say:

class BigInt
{
public:
BigInt(int bits_storage);
BigInt& operator + (BigInt);
int& operator + (int);

private:
unsigned long *storage;
int significant_bits;
}

I will leave the implementation as an excercise for the reader.
 
Reply With Quote
 
deancoo
Guest
Posts: n/a
 
      03-05-2005

"Prog37" <(E-Mail Removed)> wrote in message
news:(E-Mail Removed)...
> deancoo wrote:
>
>>
>> Would anyone in their right mind overflow a data type and still use it?
>> Does it overflow consistently? I guess what I'm asking is, should I use
>> it? What other options exist if you need to generate a number larger than
>> 2^32, which is only used as a key for unique identification? I've
>> already confirmed that for my finite set of data, the overflowed data
>> type maintains uniqueness.

>
> Does your unique key fit in 32 bits or not?


You see, the key that's generated has a large range, but is very disjointed.
There are about 2.6M elements in a range as large as aprox. 4.7B. The key
generator is super simple and super fast, so I don't want to change it. The
only drawback, of course, is how disjointed the keys are, requiring a large
container to hold them. When I said that the key maintains its uniqueness,
what I meant was that even when the key generator produces a number in
excess of 2^32, the resultant number stays unique compared to all other
generated keys. So really, is it so bad to use this overflowed data type?
Remember, I said finite set of data, and I've verified each possible key.


 
Reply With Quote
 
Richard Cavell
Guest
Posts: n/a
 
      03-05-2005
On 5/3/05 1:35 PM, deancoo wrote:

> Would anyone in their right mind overflow a data type and still use it?


I have an application where I create bitmasks by doing this:

unsigned int i32_BitMask = ( 1 << x ) - 1 ;

where x is the number of 1 bits in the bitmask.

In the case where x is 32, the 1 shifts off the left end of the 32-bit
datum, and gives me precisely what I want.

> What other options exist if you need to generate a number larger than 2^32,


You can use a larger int type like long long (GCC) or _int64 (MSVC).
 
Reply With Quote
 
Prog37
Guest
Posts: n/a
 
      03-05-2005
deancoo wrote:

>
> You see, the key that's generated has a large range, but is very disjointed.
> There are about 2.6M elements in a range as large as aprox. 4.7B. The key
> generator is super simple and super fast, so I don't want to change it. The
> only drawback, of course, is how disjointed the keys are, requiring a large
> container to hold them. When I said that the key maintains its uniqueness,
> what I meant was that even when the key generator produces a number in
> excess of 2^32, the resultant number stays unique compared to all other
> generated keys. So really, is it so bad to use this overflowed data type?
> Remember, I said finite set of data, and I've verified each possible key.
>



If I understand you correctly, you are saying that the key generator
generates keys that have a dynamic range of zero to 4.7 billion.
If this is correct you need a 33 bit unsigned integer to store the
keys without discarding any bits of key data.

ln(4.7x10^9)/ln(2) = 32.130013610776536155133366190146

or

2^32.130013610776536155133366190146 == 4.7 x 10^9


But since the number of keys generated is small you think you can
"risk it" and use the "overflowed data type".

The obvious problem is that unless your key generator prevents it
somehow there is a finite probability that multiple valid keys
will map to the same "overflowed data" value.

The only way your key generator could prevent that is if there
were key ranges that were illegal for some reason. As an example
if your key generator only produced even number keys that would
reduce the randomness of the key generation by 1 bit so you could
simply store key/2 in a 32 bit unsigned variable.

If your key generation algorithm really requires 33 bits of storage
it would be foolish to try to store it in 32 bits. You would be laying
the groundwork for a bug that only surfaces once in a while. You can
calculate the probabilities based on the number of keys generated.

I hate trying to debug problems that only happen once in a while,
I would much rather debug a repeatable bug. Just my 2 cents.

knock 2 bits of randomness off of the key generation.
In the example provided although the key could require 33 bits
 
Reply With Quote
 
Prog37
Guest
Posts: n/a
 
      03-05-2005
Richard Cavell wrote:
> On 5/3/05 1:35 PM, deancoo wrote:
>
>> Would anyone in their right mind overflow a data type and still use it?

>
>
> I have an application where I create bitmasks by doing this:
>
> unsigned int i32_BitMask = ( 1 << x ) - 1 ;
>
> where x is the number of 1 bits in the bitmask.
>
> In the case where x is 32, the 1 shifts off the left end of the 32-bit
> datum, and gives me precisely what I want.
>
>> What other options exist if you need to generate a number larger than
>> 2^32,

>
>
> You can use a larger int type like long long (GCC) or _int64 (MSVC).


For the problem he is describing he needs more than 32 bits (see my
other post).

One way of dealing with the portability issues introduced by 64 bit ints
is to use conditional compilation. He could do something like.

#ifdef WIN32
typedef _int64 big_integer;
#else
typedef long long big_integer;
#endif
 
Reply With Quote
 
Pete Becker
Guest
Posts: n/a
 
      03-05-2005
deancoo wrote:
> When you increase the number contained within an integer or long data type
> beyond its capacity, what happens? I've run into this situation, and it
> continues right along. Is it simply just rolling over when it gets to its
> limit? Curious.
>


The behavior of overflow for signed itegral types is undefined. But for
what you're doing it sounds like you should be using an unsigned type.
On overflow the result is reduced modulo 2^n, where n is the number of
bits in the value's representation.

--

Pete Becker
Dinkumware, Ltd. (http://www.dinkumware.com)
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Size of Integer , long Integer, Long double Suresh V C++ 5 07-05-2010 08:09 AM
Having compilation error: no match for call to (const __gnu_cxx::hash<long long int>) (const long long int&) veryhotsausage C++ 1 07-04-2008 05:41 PM
How to printf a long long data type integer? music4 C Programming 3 01-05-2004 03:29 AM
Re: long long integer and double precision number cyberdude C Programming 2 06-25-2003 07:54 PM
Re: long long integer and double precision number Dan Pop C Programming 0 06-24-2003 12:11 PM



Advertisments