How do I round an integer down to the nearest multiple of a number?

Question

I'm trying to round an integer to the nearest multiple of a number.

Say the number is equal to 80.

Is there a more efficient way to do this than x -= (x % the_number)?

Here's an example:

#include <stdio.h>

int main(void)
{
        int x = 191;
        int the_number = 80;
        printf("x == %d\n", x);
        x -= (x % the_number);
        printf("x - (x %% the_number) == %d\n", x);
        return 0;
}

Here's another example. It's not a fully working program like the previous is, but it's clearer what I'm trying to do:

#define LIGHT_GRAY 0x0700
#define COLUMNS 80

void pm_putchar(int c, void **ptr)
{
        c &= 0xff;
        c |= LIGHT_GRAY;

        if(c == '\n' | LIGHT_GRAY)
                *ptr += COLUMNS;
        else if(c == '\r' | LIGHT_GRAY)
                *ptr -= (*ptr % COLUMNS);

        **(short **)ptr = (short)c;
        (*ptr) += 2;
}

In the above example, assume *ptr is equal to or above the location of the VGA Text Buffer (0x0b8000).

"Is there a more efficient way to do this than x -= (x % the_number)?" Given that that operation is O(1), how efficient are you hoping to get? — Govind Parmar, May 02 '19 at 21:47
How do you know it's not "efficient"? Just because there seems to be many operations going on, doesn't mean it's inefficient. Have you looked at the generated machine code or benchmarked/profiles/timed it (with optimizations enabled)? — Some programmer dude, May 02 '19 at 21:49
I know that the `div` instruction takes up a lot of CPU time. — S.S. Anne, May 02 '19 at 22:04

score 4 · Answer 1 · answered May 02 '19 at 21:48

Well if you're only trying to work with an integer divisor (the number you're dividing by) there's always ((int) x / theNumber) * theNumber), but whether or not that looks better is up to you. However, I don't know of any better way, but you might be able to re-purpose some of the answers on this thread.

score 3 · Accepted Answer · answered May 02 '19 at 21:54

I'm trying to round an integer to the nearest multiple of a number. [...] Is there a more efficient way to do this than x -= (x % the_number)?

In the general case, no. There are alternatives with similar efficiency, such as

x = (x / the_number) * the_number

, but you're not going to do it with fewer than two arithmetic operations. (Also - is more efficient than * on some architectures, and / and % generally are about equivalent in efficiency).

If you want to truncate to a known-in-advance power of 2, however, then you can do it by masking off the lower-order bits with a single bitwise &. For instance, to truncate to the nearest lower multiple of 16 (== 0x10), you could write

x &= ~0xf;  // truncate an int x to a multiple of 16

Could you do it with any number by using `x &= ~the_number`? — S.S. Anne, May 02 '19 at 22:06
No, @JL2210. That would not have the effect of truncation to a multiple of `the_number`, neither in the general case nor in the power-of-two case, unless possibly for very specific combinations of `x` and `the_number`. Try some examples if you like. — John Bollinger, May 02 '19 at 22:12

score 3 · Answer 3 · answered May 02 '19 at 21:59

there is only one way to check:

int r1(int r, const int n)
{
    return r -= (r % n);
}

int r2(int r, const int n)
{
    return (r / n) * n;
}

and the generated code

r1:
        mov     eax, edi
        cdq
        idiv    esi
        mov     eax, edi
        sub     eax, edx
        ret
r2:
        mov     eax, edi
        cdq
        idiv    esi
        imul    eax, esi
        ret

the div/mul method has less instructions but imul will be probably slower taking into consideration latency and execution times.

score 0 · Answer 4 · answered May 03 '19 at 01:16

It is worth it to check for single bit divisors and handle the mod with a shift and mask if you suspect the value might be a power of two. There is a diminishing return for small number of bits, but possibly worthwhile.

if (!(b & (b-1))) {
    x = a & (b-1);
} else {
    x = a % b;
}

I am a bit surprised the cpu doesn't shortcut this simple case, it seems to make a factor of 4-5 on random 64bit mods.

How do I round an integer down to the nearest multiple of a number?

4 Answers4