(C - Algorithm for Bitwise operation on Modulus for number of not a power of 2)这个问题的出现的原因以及解决方法：
有一种特殊的情况，其中包括数字5。
由于16 ≡ 1 (mod 5)，您可以将变量分割为4位的nibble，查找每个nibble的模数，并将这些值相加以获得原始数字的模数。
该程序使用了位字段、查找表和加法。它也适用于模数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的任意幂对5取模等于1。因此，无论您的字长w是2⁸、2ⁱ⁶、2³²还是2⁶⁴，您都可以将大数写成a₀w⁰ + a₁w¹ + a₂w² + ... ≅ a₀1⁰ + a₁1¹ + a₂1² + ... ≡ a₀ + a₁ + a₂ + ... (mod 5)。这也是为什么任何数的十进制数字之和对3或9的模数都等于原始数的模数的原因：10 ≡ 1 (mod 3)。

这也适用于3、5、15和17在字节上，255和257在16位字上，以及65,535和65,537在32位字上。如果您注意到模式，那是因为b²ⁿ = (bⁿ+1)(bⁿ-1) + 1，其中b = 2，n = 2, 4, 8或16。

您可以将这种方法应用于任何使得块大小对n取模等于-1 (mod n)的n：交替进行加法和减法。这是因为a₀w⁰ + a₁w¹ + a₂w² + ... ≡ a₀(-1)⁰ + a₁(-1)¹ + a₂(-1)² + ... ≡ a₀ - a₁ + a₂ - ... (mod n)，但是这种方法不太有用，因为许多这样的n值都是梅森素数。这类似于通过从右向左进行加法和减法来取任何十进制数的模11，例如144 ≅ 4 - 4 + 1 ≡ 1 (mod 11)。就像数字一样，您也可以使用五位块进行相同的技巧，因为32和10也都是对11取模的-1。

当w ≡ w² ≡ c (mod b)时，另一个有用的特殊情况出现了。那么，您有a₀w⁰ + a₁w¹ + a₂w² + ... ≡ a₀·1 + a₁c + a₂c + ... ≡ a₀ + c(a₁ + a₂ + ...) (mod b)。这类似于10 ≡ 100 ≡ 1000 ≡ ... ≡ 4 (mod 6)，因此任何数字都等于它的最后一位加上其余位数的总和乘以4，对6取模。计算可以是每个字节的查找和加法，以及乘以一个小常数，可以使用位移或两个位移来完成。例如，要对20取模，您可以对除最低位字节外的所有字节进行模20相加，然后将总和乘以256模20=16，这只是一个左移4位，然后再加上最后一个字节。这可能非常方便：不计算给出余数为1或0的数字，这适用于对6、10和12的nibble取模，以及对这些值和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 ≡ 1 mod 7，所以您可以找到被11和7除的余数，这决定了被77除的余数。大多数小的素数都属于前面讨论过的特殊情况。

许多后来的RISC架构具有硬件除法但没有模运算，并告诉程序员通过计算a-(a/b)*b来计算a%b。现在最常使用的是ARM A64。如果您也没有硬件除法，请查看这个答案。另一种当基数是一个小常数时的方法示例可以在这里找到，并且广泛用于CISC架构。

还有一种算法可以计算一个比2的幂少1的数的模数。它类似于我上面使用的技术，但依赖于位移，并且可以扩展到任何因子为(1<

一般来说，您的优化编译器应该已经使用最有效的方法在您的硬件上实现%。在您的示例中，任何合理的编译器都将将常量折叠并将7%5优化为2。

除非它是x%y。那么没有其他办法-只有除法BTW x86除法与ARM相比非常慢。

您可以提供奖励。 🙂

虽然链接的代码可能来自2001年，但底层算法看起来像是将旧的“除以九”技术映射到二进制世界，而不是十进制（用于形如基数-1的除数的模数）。我相当确定在2000年之前，人们在二进制世界中重新发现了这种映射。还有与除以(base+1)的模数相关的技术，交替添加和减去代替始终添加数字。

是的，没错，我和其他许多人都注意到了这一点（尽管“除以七”似乎更常用于不同的技术）。您可以交替进行加法和减法，以找到m % n，其中块大小对n取模等于-1 (mod n)。

然而，base+1比起base-1来说是没有那么有用，因为常见的字长值对应的n是梅森素数。

我同意(base+1)的情况比(base-1)的情况更没有用。这是我30年的位运算经验。

令人印象深刻的分析！该方法仅适用于正数值，并且您拒绝负输入，但是无法输入大的无符号值，例如0xffffffffffffffff。您可以将n定义为uint64_t，检查参数中的'-'，并使用%llu。

没有一种通用的方法可以在不进行除法运算的情况下找到除法余数。

二的幂是一个例外，因为二进制表示法使得您可以使用移位来除以二。与允许您通过从末尾删除数字来将十进制数字除以十的原理相同。

显然，没有什么能阻止您编写使用位操作进行除法。您还需要编写减法，因为该算法将其作为“基本操作”所需。可以想象，这将非常慢。

r = a％2 等同于 r = a＆0x1

而2是一个2的幂（2的1次方）。那么你的观点是什么？

我的观点是，您不必除以2来得到余数，也不必移位或执行任何操作。

所以你的评论基本上意味着“我完全同意这个答案的每个细节。”？

关键词是 generalized 。对于特定的值，必须精心设计任何位移算法。

是和否！是指您不能这样做，但不是指“二的幂是一个例外，因为二进制表示法使您可以使用移位除以二。”这是正确的，但这不是一个很好的解释。

我明白了，我期待着您在您肯定正在撰写的答案中更好的解释。

哈哈，我不是要猛烈抨击他的答案:(天哪，我只是想改进它。我已经编辑过答案，但必须获得批准。

当 a 是一个 int 或任何签名类型时， r = a％2 不等于 r = a＆0x1 。

你是对的，这仅适用于大于 0 的值，我可以更加精确，但我的观点是不需要除法或移位来找到余数。

：你当然是对的！我总是忘记这种对零舍入除法的令人讨厌的后果。