我知道可以使用按位运算符计算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( "%un", 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的幂,只需将数字从末尾删除即可。
显然,没有什么能阻止你使用位操作编写分区 。 您还需要对减法进行编码,因为算法需要将其作为“基本操作”。 你可以想象,这将是非常缓慢的。
以上就是c/c++开发分享C – 对模数的按位运算的算法,对于非2的幂次数相关内容,想了解更多C/C++开发(异常处理)及C/C++游戏开发关注计算机技术网(www.ctvol.com)!)。
本文来自网络收集,不代表计算机技术网立场,如涉及侵权请联系管理员删除。
ctvol管理联系方式QQ:251552304
本文章地址:https://www.ctvol.com/c-cdevelopment/559972.html