我很想了解mod运算背后的逻辑，因为我知道可以执行移位运算来做不同的事情，比如移位乘。
我可以看到的一种方法是通过递归算法来完成，该算法不断进行除法，直到你无法再进行除法，但这似乎并不有效。
任何想法都会有所帮助。提前感谢！
快速版本是：取决于硬件、优化器、是否除以常数（pdf）、是否有异常需要检查（例如，以0为模）、是否以及如何处理负数（这对C++来说是一个可怕的问题）等
对于无符号整数，R给出了一个简洁明了的答案，但除非你精通C.，否则很难理解
R所揭示的技术的关键是去除q的倍数，直到不再存在q的倍数。我们可以天真地用一个简单的循环来做到这一点：
while (p >= q) p -= q; // One liner, woohoo!
代码可能很短，但对于p的大值和q的小值，这可能需要很长时间。
与其一次剥离一个q，不如一次剥离多个q。注意，我们实际上想去掉尽可能多的q——也就是说，floor(p/q)和q。。。事实上，这是一种有效的技术。对于无符号整数，可以预期p % q == p - (p / q) * q。（注意，无符号整数除法向下取整。）
但这几乎感觉像是作弊，因为除法和余数运算是如此密切相关。（事实上，如果硬件本身支持除法，它通常支持除法和计算余数运算，因为它们之间的关系非常密切。）
假设我们无法进行除法运算，我们如何找到大于1的q的倍数？在硬件中，固定移位运算是廉价的（如果不是实际免费的话），并且在概念上表示乘以2的非负幂。例如，将一个比特串左移3相当于乘以8（即2^3），例如，5十进制相当于"101"二进制。通过在右边加三个零（给出101000），将二进制的"101"移位，结果是十进制的50——五乘八。
同样，轮班操作作为软件操作非常便宜，你很难快速找到不支持它们的控制器。（一些体系结构，如ARM，甚至可以将移位和其他指令结合起来，使它们在很大程度上"自由"。）
武装（无法抵抗）这些轮班操作，我们可以按如下方式进行：
- 求出两个的最大幂，我们可以将
q乘以，并且仍然小于p - 从最大二次方到最小，将
q乘以每二次方，如果小于p的剩余值，则从p的剩余值中减去 - 剩下的就是剩下的
为什么这样做？因为最后你会发现，二的所有相减幂实际上加起来就是floor(p / q)！不要相信我的话，类似的知识已经知道很长时间了。
分解R的答案：
#define HI (-1U-(-1U/2))
这有效地为您提供了一个只有最高值位集的无符号整数。
unsigned i;
for (i=0; !(HI & (q<<i)); i++);
这一行实际上找到了在溢出无符号整数之前可以乘以的两个q的最高幂。这并不是绝对必要的，但除了增加所需的执行时间外，它不会改变结果。
如果你不熟悉这行中的C-ism：
- CCD_ 17是CCD_。回想一下，这相当于乘以2^
i - CCD_ 20执行逐位AND。由于CCD_ 21仅填充其顶部比特，这将仅在CCD_。再向左移动一次，就会出现整数溢出
- 当
(HI & (q<<i))为零时，!(HI & (q<<i))为"true"，否则为"false"
do { if (p >= (q<<i)) p -= (q<<i); } while (i--);
这是一个简单的递减循环CCD_ 26。注意，后递减用于i，因此循环执行，然后检查i是否不为零，然后从i中减去一，然后如果其先前的检查导致true，则继续。这具有当i为0时循环最后一次执行的属性。这一点很重要，因为我们可能需要去掉q的未相乘副本。
if (p >= (q<<i))检查2^i*q是否小于或等于p。如果是，p -= (q<<i)会将其剥离。
剩下的就剩下了。
虽然大多数C实现都在有除法指令的硬件上运行，但对于计算p%q，余数运算可以大致这样执行，假设无符号值：
#define HI (-1U-(-1U/2))
unsigned i;
for (i=0; !(HI & (q<<i)); i++);
do { if (p >= (q<<i)) p -= (q<<i); } while (i--);
得到的余数在p中。
正如R..所建议的那样，除了硬件指令和使用移位的实现之外，还有倒数乘法。
当%的右侧是一个常数时，可以使用此技术，在编译时已知
倒数乘法用于实现除法，但基于公式a%b == a-(a/b)*b，将其用于%很容易。
根据优化器的智能，有一个模基2的快捷方式。例如，a % 32可以被实现为a & 31。一般情况下，a % (2^N) == a & (2^N -1)。与分裂相比，这是闪电般的快。大多数除法器（任何硬件）都需要对结果的每一位进行至少1个周期的计算，而逻辑AND只是几个周期的操作（在流水线中）。
EDIT：仅当a未签名时才有效！