开发者

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 src

Note: 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.

0

上一篇:

下一篇:

精彩评论

暂无评论...
验证码 换一张
取 消

最新问答

问答排行榜