13

Is there some cool algorithm with bit wise operations?

Nate
  • 1,889
  • 1
  • 20
  • 40
  • 1
    being that you note assembly it sounds like you want to know this at a very low level, not something for `x MOD y` like 'repeatedly substract y from x until result is less than y' right? Reminds me of writing mul/div routines in a assembly course and being amazed how long they needed to be – jon_darkstar Mar 28 '11 at 04:09
  • Correct, I am wondering if there is some clever low level way that it is done in better than O(n) time. – Nate Mar 28 '11 at 04:13
  • I'm not sure what the hardware does, but in most instruction sets `modulus` and `division` are done using the same instruction. The division instruction is implemented such that the quotient will be output to one register and the remainder simultaneously output to a second register. – aroth Mar 28 '11 at 04:14
  • 1
    @aroth - that is familiar now that you mention it. to follow a hunch - perhaps for `x / y` x is put in one register from which y is repeatedly substracted. at each subtraction another register is incremented. these two registers are the quotient and remainder – jon_darkstar Mar 28 '11 at 04:39
  • See: http://stackoverflow.com/questions/5189631/how-can-i-take-mod-of-a-number-in-assembly-in-motorola-m6800/5189800#5189800. – Jerry Coffin Mar 28 '11 at 04:59

6 Answers6

9

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.

Reinderien
  • 11,755
  • 5
  • 49
  • 77
5

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.

Mike Lewis
  • 63,433
  • 20
  • 141
  • 111
5

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)).

Thomas Pornin
  • 72,986
  • 14
  • 147
  • 189
  • [Why does GCC use multiplication by a strange number in implementing integer division?](https://stackoverflow.com/a/41185802) explains how fixed-point multiplicative inverses work, in an easy-to-understand way. – Peter Cordes Oct 27 '18 at 02:01
4

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

Necrolis
  • 25,836
  • 3
  • 63
  • 101
3

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.

Community
  • 1
  • 1
Giacomo Pellicci
  • 105
  • 9
3

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

where (x/y) is an integer divide.

Vagrant
  • 1,696
  • 12
  • 19