C – 对模数的按位运算的算法，对于非2的幂次数
我知道可以使用按位运算符计算2的幂的模数
x % 2^n == x & (2^n - 1). 但我想知道是否存在任何通用的按位算法来查找任何数的模数不是2的幂。例如，
7%5
先感谢您。
有一对，特殊情况，包括5。
由于16≡1（mod 5），你可以做的一个技巧是将你的变量分成4位半字节，查找表中每个半字节的模数，并将这些值加在一起以得到它们的模数原始号码。
该程序使用位域，表查找和添加。 它也可以用于模3或15，并且可以扩展到具有更大查找表的更大块。
#include #include #include #include typedef struct bitfield64_t { uint64_t b0 : 4; uint64_t b1 : 4; uint64_t b2 : 4; uint64_t b3 : 4; uint64_t b4 : 4; uint64_t b5 : 4; uint64_t b6 : 4; uint64_t b7 : 4; uint64_t b8 : 4; uint64_t b9 : 4; uint64_t b10 : 4; uint64_t b11 : 4; uint64_t b12 : 4; uint64_t b13 : 4; uint64_t b14 : 4; uint64_t b15 : 4; } bitfield64_t; typedef union pun64_t { uint64_t u; bitfield64_t b; } pun64_t; /* i%5 for i in [0,19]. The upper bound guarantees that nibble_mod5[a+b] is * valid whenever a<16 and b<5. */ const unsigned nibble_mod5[20] = { 0, 1, 2, 3, 4, 0, 1, 2, 3, 4, 0, 1, 2, 3, 4, 0, 1, 2, 3, 4 }; unsigned add_mod5( const unsigned a, const unsigned b ) /* Returns (a + b) % 5, where * a < 16 * b < 5 */ { assert(a < 16); assert(b < 5); return nibble_mod5[a + b]; } int main( const int argc, const char* argv[] ) { int64_t n; if ( argc != 2 ) { fprintf( stderr, "Call this program with an unsigned number as its argument.\n" ); return EXIT_FAILURE; } if ( 1 != sscanf( argv[1], "%lld", &n ) || n < 0 ) { fprintf( stderr, "The argument must be an unsigned number.\n" ); return EXIT_FAILURE; } const pun64_t p = { .u = (uint64_t)n }; const unsigned result = add_mod5( pbb15, add_mod5( pbb14, add_mod5( pbb13, add_mod5( pbb12, add_mod5( pbb11, add_mod5( pbb10, add_mod5( pbb9, add_mod5( pbb8, add_mod5( pbb7, add_mod5( pbb6, add_mod5( pbb5, add_mod5( pbb4, add_mod5( pbb3, add_mod5( pbb2, add_mod5( pbb1, nibble_mod5[pbb0] ))))))))))))))); printf( "%u\n", result ); assert( result == n % 5 ); return EXIT_SUCCESS; }
为了找到bignum的模数，你可以利用16的任何幂与1模5相等的事实。因此，无论你的字大小是2是2ⁱ⁶，2ⁱ⁶，2³还是2⁶⁴，你都可以把你的bignum写成一个0w⁰ + a 1w 1 + a 2w 2 + ... a a1 1 + a 1 11 + a 21 2 + ...≡a0+ a 1 + a 2 + ...（mod 5）。 这也是为什么任何数字的十进制数字的总和与模数3或9的原始数字一致：10≡1（mod 3）。
这也适用于3字节，5字节，15字节和17字节，16位字的因子为255和257，32位字的因子为65,535和65,537。 如果您注意到该模式，那是因为b²ⁿ=（bⁿ+ 1）（bⁿ-1）+ 1，其中b = 2且n = 2,4,8或16。
您可以将此方法的变体应用于任何n，使得块大小与-1（mod n）一致：交替加法和减法。 它的工作原理是因为a⁰w⁰+a1w¹+ a2w2 + ...≡a0（-1）⁰+ a 1（-1）¹+ a 2（-1）²+ ...≡a0 - a 1 + a 2 - ...（mod n ），但是没那么有用，因为许多这样的n值都是梅森素数。 它类似于你如何通过从右到左并加上，减去，加上和减去数字来获取任何小数的mod 11，例如144≅4 - 4 +1≡1（mod 11）。 就像数字一样，你可以使用五位块执行相同的技巧，因为32（如10）也与-1 modulo 11一致。
另一个有用的特例是当w≡w²≡c（mod b）时。 然后你有一个δw⁰+ a1w1 + a2w2 + ......≡ac+ a1c + a2c + ......≡a0+ c（a 1 + a 2 + ...）（mod b）。 这类似于10≡100≡1000≡...≡4（mod 6）的方式，因此任何数字都与其最后一位数字相加，加上其余数字之和的四倍，模数为6.计算可以是查找和每个字节加一个，乘以一个小常数乘以一个或两个位移。 例如，要采用mod 20，您可以添加除最低位字节mod 20之外的所有字节，将和乘以256 mod 20 = 16，这只是左移4，然后添加最后一个字节。 这可能非常方便：不计算给出1或0的余数的数字，这适用于模数为6,10和12的半字节，以及以这些值为模的字节和20,24,30,34,40,48,60,68 ，80,96,102,120,136,160,170,192,204和240。
如果数字可以表示为特殊情况的乘积，则可以使用中国剩余定理求解。 例如，77 = 11×7,32≡-1 mod 11和8≡1mod 7，因此你可以找到余数除以11和7，它们确定余数除以77.大多数小素数都归为1以前讨论过的特殊情况。
许多后来的RISC架构具有硬件鸿沟但不具有模数，并且告诉程序员通过计算a-(a/b)*b来计算a%b a-(a/b)*b 。 ARM A64是目前使用最多的产品。 如果您没有硬件部门， 请查看此答案 。 这里给出了当基数是小常数时的另一种方法的示例，并且广泛用于CISC架构。
Sean Anderson在2001年也编写了一个算法，但可能早些时候发现它的计算模数比2的幂小1。它类似于我上面使用的技术，但依赖于位移，可以扩展到任何因子(1<
通常，优化编译器应该使用最有效的方法在硬件上实现% 。 在您的示例中，任何体面的编译器都只会折叠常量并优化7%5到2 。
不，没有普遍的方法可以在没有实际划分的情况下找到除法余数。
由于二进制表示，两个幂是一个例外，它允许你使用移位除以二。 同样的原则就是允许你将十进制数除以10的幂，只需将数字从末尾删除即可。
显然，没有什么能阻止你使用位操作编写分区 。 您还需要对减法进行编码，因为算法需要将其作为“基本操作”。 你可以想象，这将是非常缓慢的。