Faster modulus in C/C#?

Question

Is there a trick for creating a faster integer modulus than the standard % operator for particular bases?

For my program, I'd be looking for around 1000-4000 (e.g. n%2048). Is there a quicker way to perform n modulus 2048 than simply: n%2048?

Answer 1

If the denominator is known at compile time to be a power of 2, like your example of 2048, you could subtract 1 and do a bitwise-and.

That is:

n % m == n & (m - 1) 

...where m is a power of 2.

For example:

22 % 8 == 22 - 16 == 6

         Dec   Bin
       -----   -----
          22 = 10110
           8 = 01000  
       8 - 1 = 00111 
22 & (8 - 1) =   10110 
               & 00111 
               -------
           6 =   00110

Bear in mind that a good compiler will have its own optimizations for %, maybe even enough to be as fast as the above technique. Arithmetic operators tend to be pretty heavily optimized.