

Join them; it only takes a minute:

Sign up
Join the Stack Overflow community to:
  1. Ask programming questions
  2. Answer and help your peers
  3. Get recognized for your expertise

It is told that modulo operator "%" and divide operator "/" are very inefficient in embedded C++.

How can I alternatively achieve the following expression:

a = b % c;

I understand that this can be achieved using the following logic:

a = b - c;
while (a >= c) {
  a = a - c;

But my question is, is this code involving while loops efficient enough, compared to % operator?

Thanks, Kirti

share|improve this question
"is this code involving while loops efficient enough, compared to % operator?" You tell us, you're the one using the program. Does it feel slow? Can you even notice? Have you profiled and found this to be slow at all? – GManNickG Nov 15 '11 at 6:11
That will depend on the size. If b = 1000000000 and c = 3. It will take a while... – Mysticial Nov 15 '11 at 6:12
Can you tell target CPU and compiler? Without that it is impossible to compare any approaches. – user1034749 Nov 15 '11 at 6:12
You might try to profile different versions to see what is more appropriate in you enviroment. Did you try to do it? I think in more % is rather effective in most case. – Oleg Nov 15 '11 at 6:13
Since you have both the versions of implementing this, Why not just profile both in your envrionment and get the results for yourself,those will be much more conclusive than any answers,which would make wise guesses or approximations about your envrionment. – Alok Save Nov 15 '11 at 6:14
up vote 5 down vote accepted

Nothing is going to be considerably more efficient than the % operator. If there was a better way to do it, then any reasonable compiler would automatically convert it. When you're told that % and / are inefficient, that's just because those are difficult operations - if you need to perform a modulo, then do that.

There may be special cases when there are better ways - for example, mod a power of two can be written as a binary or - but those are probably optimized by your compiler.

share|improve this answer

Division and modulus are indeed costly hardware operations, whatever you do (this is more related to hardware architecture than to languages or compilers), perhaps ten times slower than addition.

However, on current laptops or servers, and on high-end microcontrollers, cache misses are often much slower than divisions!

The GCC compiler is often able to optimize them, when the divisor is a constant.

Your naive loop is usually much more slower than using the hardware division instruction (or the library routine doing it, if not provided by hardware). I believe you are wrong in avoiding the division & replacing it with your loop.

You might tune your algorithms -e.g. by having power of twos- but I don't recommend using your code. Remember that premature optimization is evil so first try to get your program correct, then profile it to find the trouble spots.

share|improve this answer
+1 for getting the program right before worrying about optimization. The cause of many a failed project. – Dan Nov 15 '11 at 6:21
Quotes are better when complete: We should forget about small efficiencies, say about 97% of the time: premature optimization is the root of all evil, good answer otherwise. – Matthieu M. Nov 15 '11 at 8:13

That code will almost certainly be slower than however your processor/compiler decides to perform the divide/mod. Generally, shortcuts are pretty hard to come by for basic arithmetic operators, since the mcu/cpu designers and compiler programmers are pretty good at optimizing this for almost all applications.

One common shortcut in embedded devices (where every cycle/byte can make a difference) is to keep everything in terms of base-2 to use the bit shift operators to perform multiplication and division, and the bitwise and (&) to perform modulo.


unsigned int x = 100;
unsigned int y1 = x << 4;   // same as x * 2^4 = x*16
unsigned int y2 = x >> 6;   // same as x * 2^6 = x/64
unsigned int y3 = x & 0x07; // same as x % 8
share|improve this answer
Any decent compiler will make the same optimization for you when the right operand is a power-of-two constant. The bit-shifting/masking trick is a leftover from the early days when compiler optimization sucked, and should no longer be necessary. – Emile Cormier Nov 15 '11 at 6:24
In the embedded world you unfortunately don't always have the luxury of a decent compiler... I agree in the general case, but when in doubt, a quick check of the dissassembly will determine whether this will help or not. – shenles Nov 15 '11 at 6:29

If the divisor is known at compile time, the operation can be transformed into a multiplication by a reciprocal, with some shifts, adds, and other fast operations. This will be faster on any modern processor, even if it implements division in hardware. Embedded targets usually have highly optimized routines for divide / modulo, since these operations are required by the standard.

share|improve this answer

If you have profiled your code carefully and found that a modulo operator is the major cost in an inner loop then there is an optimisation that might help. You might be already familiar with the trick for determining the sign of an integer using arithmetic left shifts (for 32 bit values):

sign = ( x >> 31 ) | 1;

This extends the sign bit across the word, so negative values yield -1 and positive values 0. Then bit 0 is set so that positive values result in 1.

If we're only incrementing values by a quantity that is less than the modulo then this same trick can be used to wrap the result:

val += inc;
val -= modulo & ( static_cast< int32_t >( ( ( modulo - 1 ) - val ) ) >> 31 );

Alternatively, if you are decrementing by values less than the modulo then the relevant code is:

int32_t signedVal = static_cast< int32_t >( val - dec );
val = signedVal + ( modulo & ( signedVal >> 31 ) );

I've added the static_cast operators because I was passing in uint32_t, but you might not find them necessary.

Does this help much as opposed to a simple % operator? That depends on your compiler and CPU architecture. I found a simple loop ran 60% faster on my i3 processor when compiled under VS2012, however on the ARM11 chip in the Raspberry Pi and compiling with GCC I only got a 20% improvement.

share|improve this answer

Division by a constant can be achieved by a shift if a power of 2 or a mul add shift combination for others.

http:// has x86 assembly version as well as C source in download from first post. that generates this code for you.

share|improve this answer

Your Answer


