C++ Best way to get integer division and remainder
I am just wondering, if I want to divide a by b, and am interested both in the result c and the remainder (e.g. say I have number of seconds and want to split that into minutes and seconds), what is the best way to go about it?
Would it be
int c = (int)a / b;
int d = a % b;
or
int c = (int)a / b;
int d = a - b * c;
开发者_StackOverflow
or
double tmp = a / b;
int c = (int)tmp;
int d = (int)(0.5+(tmp-c)*b);
or
maybe there is a magical function that gives one both at once?
On x86 the remainder is a by-product of the division itself so any half-decent compiler should be able to just use it (and not perform a div
again). This is probably done on other architectures too.
Instruction:
DIV
srcNote: Unsigned division. Divides accumulator (AX) by "src". If divisor is a byte value, result is put to AL and remainder to AH. If divisor is a word value, then DX:AX is divided by "src" and result is stored in AX and remainder is stored in DX.
int c = (int)a / b;
int d = a % b; /* Likely uses the result of the division. */
std::div
returns a structure with both result and remainder.
On x86 at least, g++ 4.6.1 just uses IDIVL and gets both from that single instruction.
C++ code:
void foo(int a, int b, int* c, int* d)
{
*c = a / b;
*d = a % b;
}
x86 code:
__Z3fooiiPiS_:
LFB4:
movq %rdx, %r8
movl %edi, %edx
movl %edi, %eax
sarl $31, %edx
idivl %esi
movl %eax, (%r8)
movl %edx, (%rcx)
ret
Sample code testing div() and combined division & mod. I compiled these with gcc -O3, I had to add the call to doNothing to stop the compiler from optimising everything out (output would be 0 for the division + mod solution).
Take it with a grain of salt:
#include <stdio.h>
#include <sys/time.h>
#include <stdlib.h>
extern doNothing(int,int); // Empty function in another compilation unit
int main() {
int i;
struct timeval timeval;
struct timeval timeval2;
div_t result;
gettimeofday(&timeval,NULL);
for (i = 0; i < 1000; ++i) {
result = div(i,3);
doNothing(result.quot,result.rem);
}
gettimeofday(&timeval2,NULL);
printf("%d",timeval2.tv_usec - timeval.tv_usec);
}
Outputs: 150
#include <stdio.h>
#include <sys/time.h>
#include <stdlib.h>
extern doNothing(int,int); // Empty function in another compilation unit
int main() {
int i;
struct timeval timeval;
struct timeval timeval2;
int dividend;
int rem;
gettimeofday(&timeval,NULL);
for (i = 0; i < 1000; ++i) {
dividend = i / 3;
rem = i % 3;
doNothing(dividend,rem);
}
gettimeofday(&timeval2,NULL);
printf("%d",timeval2.tv_usec - timeval.tv_usec);
}
Outputs: 25
In addition to the aforementioned std::div family of functions, there is also the std::remquo family of functions, return the rem-ainder and getting the quo-tient via a passed-in pointer.
[Edit:] It looks like std::remquo doesn't really return the quotient after all.
All else being equal, the best solution is one that clearly expresses your intent. So:
int totalSeconds = 453;
int minutes = totalSeconds / 60;
int remainingSeconds = totalSeconds % 60;
is probably the best of the three options you presented. As noted in other answers however, the div
method will calculate both values for you at once.
You cannot trust g++ 4.6.3 here with 64 bit integers on a 32 bit intel platform. a/b is computed by a call to divdi3 and a%b is computed by a call to moddi3. I can even come up with an example that computes a/b and a-b*(a/b) with these calls. So I use c=a/b and a-b*c.
The div method gives a call to a function which computes the div structure, but a function call seems inefficient on platforms which have hardware support for the integral type (i.e. 64 bit integers on 64 bit intel/amd platforms).
Many answers suggest using the following code:
int div = a / b;
int mod = a % b;
However, it is worth remembering that division, unlike multiplication, addition is performed much longer (as far as I know, dozens of times of clock cycles compared to one). And, if you need to repeatedly calculate mod and div, then it is worth replacing two divisions with one division, one multiplication and one addition as follows:
int div = a / b;
int mod = a - div * b;
You can use a modulus to get the remainder. Though @cnicutar's answer seems cleaner/more direct.
精彩评论