CODEWITHSUNDEEP
assemblybit-manipulationmodulo
Nate
Nate

Reputation: 1921

How do computers find modulus?

Is there some cool algorithm with bit wise operations?

Upvotes: 15

Views: 12521

Answers (6)

Giacomo Pellicci
Giacomo Pellicci

Reputation: 103

Also checking the modulo 2 is easy, as it only need to check the least significant bit, usually.

Quoting wikipedia:

For special cases, on some hardware, faster alternatives exist. For example, the modulo of powers of 2 can alternatively be expressed as a bitwise AND operation:

x % 2n == x & (2n - 1)

Examples (assuming x is a positive integer):

x % 2 == x & 1

x % 4 == x & 3

x % 8 == x & 7

In devices and software that implement bitwise operations more efficiently than modulo, these alternative forms can result in faster calculations.

Upvotes: 3

Thomas Pornin
Thomas Pornin

Reputation: 74412

If the divisor is known in advance (e.g. for code produced by a C compiler, this is a constant known at compile time) then integer division (from which the modulus can be easily obtained) can sometimes be implemented with a multiplication and a shift. See this article for details (warning: this is not light reading).

In many processors, integer multiplication is vastly faster than integer division; some processors do not even have an integer division opcode (multiplication on n-bit values can be optimized into a circuit of depth O(log n), whereas there is no known method to optimize a division circuit below a depth of O(n)).

Upvotes: 5

Necrolis
Necrolis

Reputation: 26171

Apart from the obvious method using DIV and IDIV (for x86) as mentioned above, the result of any number modulo'd by a power of two can be calculated by taking the bitwise and: x mod y where y is pow2 is the same as x AND (y - 1). Most compilers perform this when possible, as division is far more expensive than bitwise ops

Upvotes: 4

Vagrant
Vagrant

Reputation: 1716

x mod y = x - y*(x/y)

where (x/y) is an integer divide.

Upvotes: 4

Mike Lewis
Mike Lewis

Reputation: 64157

Most of the time, modulus is just computed by dividing the two numbers. The quotient is stored in one register, and the remainder is stored in the other register. You would go after the remainder.

Upvotes: 6

Reinderien
Reinderien

Reputation: 15243

Often, the modulus and divide operations on a processor are the same thing. For instance, refer to http://jsimlo.sk/docs/cpu/index.php/div.html . This is the implementation of the divide instruction on Intel processors.

Upvotes: 9

Related Questions