CODEWITHSUNDEEP
c++division
Cookie
Cookie

Reputation: 12692

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;

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?

Upvotes: 141

Views: 333226

Answers (9)

Alexey Ismagilov
Alexey Ismagilov

Reputation: 193

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;

Upvotes: -1

Jamin Grey
Jamin Grey

Reputation: 10495

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.

Upvotes: 7

brac37
brac37

Reputation: 71

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).

Upvotes: 5

pezcode
pezcode

Reputation: 5769

std::div returns a structure with both result and remainder.

Upvotes: 130

Greg Howell
Greg Howell

Reputation: 1945

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

Upvotes: 13

Peter Alexander
Peter Alexander

Reputation: 54300

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

Upvotes: 37

Jon
Jon

Reputation: 3065

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.

Upvotes: 5

Sinthet
Sinthet

Reputation: 893

You can use a modulus to get the remainder. Though @cnicutar's answer seems cleaner/more direct.

Upvotes: -5

cnicutar
cnicutar

Reputation: 182734

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. */

Upvotes: 136

Related Questions