I have minimize cost of calculating modulus in C. say I have a number x and n is the number which will divide x

when n == 65536 (which happens to be 2^16):

mod = x % n (11 assembly instructions as produced by GCC) or
mod = x & 0xffff which is equal to mod = x & 65535 (4 assembly instructions)

so, GCC doesn't optimize it to this extent.

In my case n is not x^(int) but is largest prime less than 2^16 which is 65521

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.