How big can a 64 bit unsigned integer be?

Question

I am quite clear about How big can a 64bit signed integer be? Thanks to this question and its straightforward answers.

So, according to that, could I say that an unsigned int can be 2^64 - 1, rather than 2^63 - 1?

2^63 - 1:    0111111111111111111111111111111111111111111111111111111111111111

2^64 - 1:    1111111111111111111111111111111111111111111111111111111111111111

If and only if I got it correctly, how can I detect an unsigned overflow? An overflow of a signed integer in two's complement representation would invade the highest bit position, returning a negative number. But how about this unsigned case?

Solution 1

It is hard or impossible to detect by looking at a value.
The problem is the maximum value plus even only 1 is still/again a valid value; i.e. 0.

This is why most programmers avoid as much as possible, if it is actually a wrong value. For some applications, wrapping around is part of the logic and fine.

If you calculate e.g. c=a+b; (a, b, c being 64bit unsigned ints and a,b being worryingly close to max, or migth be) and want to find out whether the result is affected,
then check whether ((max - b) < a); with max being the appropriate compiler-provided symbol.

Do not calculate the maximum value yourself as 2^64-1, it will be implementation specific and platform specific. On top of that, it will contain the wraparound twice (2^64 being beyond max, probably 0; and subtracting 1 going via 0 back...). And that applies even if ^ is understood to be an appropriate version of "to the power of".

Solution 2

Signed integer can only go as far as 2^63-1 (9,223,372,036,854,775,807) because the bit of highest significance is reserved for the sign. If this bit is 1 then the number is negative, and can go as low as -2^63 (-9,223,372,036,854,775,808).

On a signed 64-bit integer, 2^64-1 is actually the number -1.

If you use unsigned integers however, the value starts at 0 and 2^64-1 (18,446,744,073,709,551,615) becomes it's highest value, but unsigned integers cannot represent negative values.

Solution 3

It can be 18446744073709551615.

18,446,744,073,709,551,615
q5 q4  t   b   m   t   h

Solution 4

Your assumption for the maximum size of signed and unsigned integers is correct. The actual values are 9223372036854775807 for signed and 18446744073709551615 for unsigned.

Detecting overflow for unsigned addition is rather simple - if the result is less than either operand there was an overflow.

Subtraction is similar, if the result is greater than the first operand then you had overflow.

Multiplication is tough, I don't know a simple rule for that one.

Overflow is impossible for division unless you divide by zero.

Solution 5

How big is 64 bit?

The answer the question how big is an unsigned 64 bit integer, I will propose to do a small comparative test in assembly or any programming language that supports 64 bit data types.

Count from 0 to maximum value that can be stored in a variable. First time use a 32 bit wide variable and second time use a 64 bit wide variable. Try to estimate the results.

In C#, the code may look like this for 32 bit variable (… ignore please the off by one issue):

for (uint i = 0; i < uint.MaxValue; i++)
{
    Process(i);
}

uint.MaxValue is the number that you obtain when you set all bits of the variable to 1. It is basically equal to 2^32 – 1 = 4294967295. This is about 4.2 billion.

The test code for the case with 64 bit variable is similar:

for (ulong i = 0; i < ulong.MaxValue; i++)
{
    Process(i);
}

ulong.MaxValue is this time 2^64 – 1 = 18446744073709551615 (a 20 digit number).

At about 1 billion Process() operations / second, the first program will finish its job in:

2^32 / 1000000000 = 4.29 seconds

At the same processing speed, the second program will finish its job in:

2^64 / 1000000000 / 3600 / 24 / 365 = 585 years!

That’s quite a difference!!! Who has the time to wait 585 years for a basic for to finish its job!

And the funny part is that 1 billion operations per second is quite aggressive! For a more realistic scenario where you execute from 1 million to a couple hundred million operations per second, the time explodes to thousands even hundreds of thousands of years to do a single for!!!

For majority of people the above exercise is a fun visualization of 64 bit power. But this exercise also shows the reality faced by computer science engineers working with algorithms. A poorly implemented algorithm (e.g. search or computational problem), that takes a brute force approach, can very well ruin your software.

Other big numbers

As a recap, remember that the maximum number stored in a 64 bit register / variable is 2^64 – 1 = 18446744073709551615 (a 20 digit number). As big at it seems this number is still small when compared for instance with 1 googol which is 10^100 (1 followed by 100 zeros) !

And even the big googol is smaller than 70! (70 factorial which is 1 * 2 * … * 70). Wow! This really shows the power of multiplication!

And you know what: the googol is well within the range of the double data type (IEEE 754 floating point) – also a 64 bit structure. How double manages to store such big numbers will be presented in a future article.

I hope you had fun!

View more solutions

Comments

[Klas Lindbäck]

That would be 2^64 - 1.

[hansvb]

It is not fundamentally different from detecting overflow in a signed number. Instead of a negative number you would get a small integer.

[P.P]

Unsigned integers don't overflow; they wrap around.

[hansvb]

See the discussion here: stackoverflow.com/questions/3944505/… Best way is probably to use the CPU's overflow flags (but those are not exposed in a standard way so you need to use gcc compiler macros or something like that).

[Lundin]

"How big can a 64 bit unsigned integer be?" It can be 64 bits... For any binary (base 2) number, the digit number n has the the value val * 2^n, where val is 1 or 0 for binary. Note that the lsb is n=0. So a number with only the msb set to 1 would be 2^63 and a 64 bit number set to "all ones" would be 2^64 - 1. This is the utterly basic stuff they teach in (decent) schools before you are allowed to take any programming classes whatsoever.