title: Most optimized way to calculate modulus in C
body: <p>I have minimize cost of calculating modulus in C.
  say I have a number x and n is the number which will divide x</p>
  
  <p>when n == 65536 (which happens to be 2^16):</p>
  
  <p>mod = x % n   (11 assembly instructions as produced by GCC)
  or<br>
  mod = x &amp; 0xffff  which is equal to  mod = x &amp; 65535   (4 assembly instructions)</p>
  
  <p>so, GCC doesn't optimize it to this extent.</p>
  
  <p>In my case n is not x^(int)  but is largest prime less than 2^16 which is 65521</p>
  
  <p>as I showed for n == 2^16, bit-wise operations can optimize the computation. What bit-wise operations can I preform when n == 65521 to calculate modulus.</p>