我知道可以使用按位运算符来计算2的幂的模
x % 2^n == x & (2^n - 1).
但我想知道是否存在任何通用的按位算法来查找任何数字的模数都不是2的幂。例如，
7%5
先感谢您。
最佳答案
有一些特殊情况，包括5种。
由于16≡1(mod 5)，您可以采取的技巧是将变量拆分为4位半字节，在表中查找每个半字节的模数，然后将这些值相加以获得原始数字的模数。
该程序使用位域，表查找和加法。它也适用于模数为3或15的模数，并且可以使用更大的查找表扩展为更大的块。
#include <assert.h>
#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>
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( p.b.b15,
add_mod5( p.b.b14,
add_mod5( p.b.b13,
add_mod5( p.b.b12,
add_mod5( p.b.b11,
add_mod5( p.b.b10,
add_mod5( p.b.b9,
add_mod5( p.b.b8,
add_mod5( p.b.b7,
add_mod5( p.b.b6,
add_mod5( p.b.b5,
add_mod5( p.b.b4,
add_mod5( p.b.b3,
add_mod5( p.b.b2,
add_mod5( p.b.b1,
nibble_mod5[p.b.b0] )))))))))))))));
printf( "%u\n", result );
assert( result == n % 5 );
return EXIT_SUCCESS;
}
为了求大数的模数，您可以利用16的幂等于1模5的事实。因此，无论您的字长w是2⁸，2ⁱ⁶，2³²还是2⁶⁴，您都可以将大数写为a₀w⁰ + a 1 w 1 + a 2 w 2 +……a 1 1 + a 1 1 + a 2 1 2 +……a 1 + a 3 + a 2 +……(模5)。这也是为什么任何数字的十进制数字之和与原始数字模3或9:10≡1(mod 3)一致的原因。
这也适用于字节的3、5、15和17，16位字的系数为255和257，32位字的系数为65,535和65537。如果您注意到该模式，那是因为b²ⁿ=(bⁿ+ 1)(bⁿ-1)+1，其中b = 2且n = 2、4、8或16。
您可以将此方法的变体应用于任何n，以使块大小等于-1(mod n):交替加减。之所以起作用是因为a₀w⁰+a₁w¹+a2w²+ ...≡a₀(-1)⁰+a₁(-1)¹+a²(-1)²+ ...≡a₀-a₁+ a2-...(mod n )，但用处不大，因为n的许多这样的值都是梅森素数。这类似于您可以通过从右到左并加，减，加和减数字来获取任意小数的mod 11的方式，例如144≅4-4 +1≡1(mod 11)。就像数字一样，您可以对五位块进行相同的处理，因为32(如10)也等于-1模11。
当w≡w²c(mod b)时，会发生另一种有用的特殊情况。然后，您有aww + aww + a2w2 + ... aa·1 + acc + a2c + ... aa + c(a₁+ a2 + ...)(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模11和8 -1模7，因此您可以找到除以11和7的余数，确定除以77的余数。大多数小的素数都落入一个前面讨论的特殊情况。
许多后来的RISC架构都有硬件划分，但没有模数，并告诉程序员通过计算
a%b来计算a-(a/b)*b。 ARM A64是当今使用最多的一种。如果您也没有硬件部门，请使用check out this answer。当基数是一个小常数时，另一种方法的一个示例是here，它在CISC体系结构中得到了广泛使用。还有一种算法written by Sean Anderson in 2001 but probably discovered earlier可以以小于2的幂的整数来计算模数。它与我上面使用的技术类似，但是依赖于位移，并且可以扩展到
(1<<s)-1的任何因子。这几乎就是您要寻找的!通常，您的优化编译器应已使用最有效的方法在硬件上实现
%。在您的示例中，任何不错的编译器都将折叠常量并将7%5优化为2。关于C-模数上按位运算的算法(非2的幂)，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/49949579/