C/C#的模量越快？

Question

对于特定碱基,是否有创建比标准%运算符更快的整数模数的技巧？

对于我的程序,我会寻找大约1000-4000(例如n%2048).有没有以执行N模量2048不仅仅是一个更快的方法:n%2048？

Answer 1

如果分母在编译时已知为2的幂,就像2048的例子那样,你可以减去1并按位进行.

那是:

n % m == n & (m - 1) 

...... m2的力量在哪里.

例如:

22 % 8 == 22 - 16 == 6

         Dec   Bin
       -----   -----
          22 = 10110
           8 = 01000  
       8 - 1 = 00111 
22 & (8 - 1) =   10110 
               & 00111 
               -------
           6 =   00110

请记住,一个好的编译器会有自己的优化%,甚至可能与上述技术一样快.算术运算符往往相当优化.

Answer 2

对于2的幂2^n,您所要做的就是将除最后一位之外的所有位清零n.

例如(假设32位整数):

x%2 相当于 x & 0x00000001

x%4 相当于 x & 0x00000003

一般来说x % (2^n)等于x & (2^n-1).写在C中,这将是x & ((1<<n)-1).

这是因为2^n你在n+1第一位(右起)给你一个1 .所以2^n-1会给你n右边的那些,左边的零.