module without using %

I remember there is a way to calculate the remainder without using the % operator but cant seem to find it. Anyone knows what it was?

Divide, and subtract (quotient*divisor)?

In what situation do you need any other means of getting the remainder than using the "%" ?

When you are asked to implement modulus without using %?

I just read an implementation of the standard function div() and remembered there was a way without division and % to get the remainder. Was just curious what it was again

Without division? I don't see how that's possible, but if it is I'd like to see :P.

This page shows a way for powers of 2.

In addition, div() seems to calculate both a/b and a%b. If you have done the first, the modulo can be found without doing the same division again. That is, div() is probably meant for optimizing cases where you need both results.

int a = 10 ;
int b = 3 ;
int remainder = a - ((a/b)*b) ;

You can always emulate integer division with subtraction and counting.
By doing so, you'll get the modulus automatically.

Quote:

---

Originally Posted by KIBO

I just read an implementation of the standard function div() and remembered there was a way without division and % to get the remainder. Was just curious what it was again

---

If the number you're dividing by is small enough and is known at compile time, and the number being divided is no larger than half your register size, then to do fast division you can:
Multiply by the fixed-point inverse of the divisor, and then convert back to an integer. That's a multiply and a shift, instead of a division, making it definitely faster. You wouldn't do this for powers of two though as then you can just use a single shift.
e.g.

Code:

---

template <unsigned char n>
unsigned short div(unsigned short x)
{
    return (int)x * ((0x10000+n-1)/n) >> 16;
}

---

Mod can then be trivially based on this, though there may be a faster way also.

Code:

---

template <unsigned char n>
unsigned short mod(unsigned short x)
{
    return x - div<n>(x) * n;
}

---

Note that I'm also assuming that x is positive as I can't be bothered checking the bahviour of negatives, hence use of unsigned to make sure.

Repeated subtraction until the number is less than the divisior will also work, not that you'd want to do that of course.