Dan W - 1 month ago 7x

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

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.

Source (Stackoverflow)

Comments