Integer types with at least 64 bits have been a part of the C standard for a while now (they were added in C99, and were a standard extension in many 32-bit compilers before that). But have you ever wondered what exactly happens when you use them?
Consider the following function (substitute
long long with
__int64 if you
are using an older version of Visual C++):
let’s first have a look at what the VC 64-bit compiler gives us:
Pretty much what you would expect, a little setup and an
idiv instruction to
perform the division. Now let’s try the VC 32-bit compiler:
A little setup and .. a call?
The thing is, 32-bit x86 only has instructions for mixed mode 32/64 bit operations – with one assembly instruction you can multiply two 32-bit integers to get a 64-bit result, or you can divide a 64-bit integer by a 32-bit as long as the quotient fits in 32 bits. But to divide two 64-bit integers, you have to emulate the operation in software.
That is where the
_alldiv function comes in. It is a support function in the
C runtime library that performs a 64-bit divide. In fact there is a whole
family of such functions to do multiply, divide and shifts on 64-bit numbers
(addition and subtraction are inlined since they only require two assembly
Other compilers do likewise, for instance GCC calls
__divdi3 to perform
It is important to be aware of this, because using
long long instead of
means that arithmetic operations you probably expect to be single instructions,
all of a sudden become library calls who’s execution time can depend on the
As an example, I timed a simple implementation of the extended Euclidean algorithm with 32- and 64-bit integers. Compiling with the VC 32-bit compiler, the 64-bit version was roughly 3 times slower (depending on the CPU).