我很想理解mod操作背后的逻辑,因为我知道可以执行位移操作来执行不同的操作,例如位移到乘法.
我可以看到它完成的一种方法是通过递归算法继续划分,直到你不能再分裂,但这似乎并不高效.
任何想法都会有所帮助.提前致谢!
Kag*_*nar 14
快速版本是:取决于硬件,优化器,如果它除以常量(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.(注意无符号整数除法向下舍入.)
但这几乎就像作弊,因为分裂和剩余操作是如此密切相关.(事实上,如果硬件本身支持除法,它通常支持除法和计算余数运算,因为它们之间的关系非常紧密.)
假设我们无法访问除法,我们如何找到q大于1 的倍数来消除？在硬件中,固定移位操作很便宜(如果不是实际上没有),并且在概念上表示乘以2的非负功率.例如,将位串向左移位3相当于乘以8(即2 ^ 3),例如5位小数相当于"101"二进制.通过在右侧添加三个零(给出'101000')将结果'101'以二进制形式移位,结果为十进制50 - 五次八.
同样,转换操作作为软件操作非常便宜,而且您很难找到一个不能快速支持它们的控制器.(ARM等一些架构甚至可以将轮班与其他指令结合起来,使它们在很多时候都是"免费的".)
对于这些转换操作,ARMed(无法抗拒),我们可以按如下方式进行:
q且仍然小于的最大两个幂p.q功率,乘以2 的每个幂,如果它小于剩下的p那么从左边的数减去它p.为什么这样做？因为最后你会发现两个的所有减去的力量实际上总和了floor(p / q)!不要相信我的话,类似的知识已经知道了很长时间.
打破R的答案:
#define HI (-1U-(-1U/2))
这实际上为您提供了一个无符号整数,只设置了最高位.
unsigned i;
for (i=0; !(HI & (q<<i)); i++);
该行实际上发现两个最高功率q可以在溢出无符号整数之前相乘.这不是绝对必要的,但除了增加所需的执行时间之外,它不会改变结果.
如果您不熟悉此行中的C-isms:
(q<<i)是左移位i.回想一下这相当于乘以2 ^ i.HI & (q<<i)执行按位AND.由于HI仅填充其顶部位,因此当(q<<i)仅足以使顶部位非零时,将仅导致非零值.再向左移动一次,就会出现整数溢出.!(HI & (q<<i))当(HI & (q<<i))为零时为'true',否则为'false'.do { if (p >= (q<<i)) p -= (q<<i); } while (i--);
这是一个简单的减少循环do { .... } while (i--);.注意,后i循环用于循环执行,然后它检查是否i不为零,然后从中减去一个i,然后如果它的早期检查导致true它继续.这具有循环在i0 时执行其最后一次的属性.这很重要,因为我们可能需要去掉一个未经过复制的副本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.