Editing Modulo (section)

==Performance issues==
Modulo operations might be implemented such that a division with a remainder is calculated each time. For special cases, on some hardware, faster alternatives exist. For example, the modulo of [[powers of 2]] can alternatively be expressed as a [[Bitwise operation|bitwise]] AND operation (assuming {{math|''x''}} is a positive integer, or using a non-truncating definition):
:<code>x % 2<sup>n</sup> == x & (2<sup>n</sup> - 1)</code>

Examples:
:{{code|1=x % 2 == x & 1}}
:{{code|1=x % 4 == x & 3}}
:{{code|1=x % 8 == x & 7}}

In devices and software that implement bitwise operations more efficiently than modulo, these alternative forms can result in faster calculations.<ref>{{cite web |first= Adam |last= Horvath |url= http://blog.teamleadnet.com/2012/07/faster-division-and-modulo-operation.html |title= Faster division and modulo operation - the power of two |date= July 5, 2012}}</ref>

[[Compiler optimization]]s may recognize expressions of the form {{code|expression % constant}} where {{code|constant}} is a power of two and automatically implement them as {{code|expression & (constant-1)}}, allowing the programmer to write clearer code without compromising performance. This simple optimization is not possible for languages in which the result of the modulo operation has the sign of the dividend (including [[C (programming language)|C]]), unless the dividend is of an [[Signedness|unsigned]] integer type. This is because, if the dividend is negative, the modulo will be negative, whereas {{code|expression & (constant-1)}} will always be positive. For these languages, the equivalence <code>x % 2<sup>n</sup> == x < 0 ? x | ~(2<sup>n</sup> - 1) : x & (2<sup>n</sup> - 1)</code> has to be used instead, expressed using bitwise OR, NOT and AND operations.

Optimizations for general constant-modulus operations also exist by calculating the division first using the [[Division algorithm#Division_by_a_constant|constant-divisor optimization]].