我们有机会进行了一次小型但非常有趣的战术练习
在研究基于Cortex-M4架构的知名公司的新MK的过程中（我肯定会在后面对此进行介绍），出现了一个问题，即硬件实现中的整数除法运算能以多快的速度起作用。 全面的实验得出了一些出乎意料的结果：在处理器频率的3个时钟周期内执行了将32位数字除以32位数字的操作-好吧，不必担心它有多快。 原来，这仅发生在某些操作数上，但是进一步的研究表明，完成除法的时间不会超过7个小节。 获得的结果引起了一些匆忙（“这不是某个特定的修辞格，它不知道它是什么意思，而是一个非常具体的动词”-与往常一样，Divov是无与伦比的）。
嗯，您不能只取并快速除以这么长的数字，这很奇怪，但是事实是很固执的。 我以为俄罗斯联邦总统明天要给我打电话给他，并把我的任务定在使MK不比ARM更糟的面前（我同意这是个妄想，但世界上不会发生），但是我看着他感到困惑，并且明白我将无法在这样的时间内进行如此数量的划分，而且我将不辜负强加于我的期望（事实上，我总是可以悄悄地从ARM购买许可证，并假装自己发明了一切，很多人都这样做了，但是GDP期望与我完全不同，然后-我可以欺骗它，但我不太可能。
我为ARM的人员比我聪明得多而感到难过，于是我很想去互联网看看他们是如何做到的。 我没有在ARM网站上找到有关执行时间的任何信息，在STM32上的一种材料中表明该除法需要2到7个时钟周期，这与观察结果相对应，但是没有有关如何完成此操作的信息。
总的来说，无所不能的互联网并没有太大帮助，有一些以常数除法的技巧，我在其中一篇文章中谈到了它们，但我们的情况有所不同，有牛顿算法及其加速版本，但显然不是这种情况，有一种基于傅里叶变换，但这是非常大的数目，即使在ARM体系结构上也不太可能在7个周期内完成。 我不得不自己想出一个解决方案，发现了一个解决方案，它是如此简单和明显，以至于在制定任务之后就没有立即执行此操作，这使我感到有些尴尬。
在考虑我的决定之前，我建议您先找到自己的，然后与我的比较，如果两者有所不同，我会在评论中等待您。
因此，我们如何快速（在不超过7个周期内）将两个32位数字相除以获得32位结果。
首先，我们回想一下通常如何在二进制算术中进行除法
经典形式。 该算法非常简单明了-我们从除数中减去除数。 如果结果为非负数（我们将无符号数字相除），则使结果的下一位等于1，然后将结果视为下一个被除数，否则结果的下一位为0。在下一个小数之前，我们将除数减半（将其除以右边，或将股息向左移动），并将位权重降低2倍（通过类似的移动）。 因此，我们在一个时钟周期中得到了一位结果，整个操作将持续32个时钟周期。 在此过程中仍存在最初的转变，但它不会影响对整体情况的评估。 我们会加速，但是如何呢？
我们注意到，最终的算法非常类似于具有顺序逼近的ADC的操作，并且回想起还有其他转换方法，速度更快-并行转换。 如果...
我们将不仅从除数中减去除数，还从除数中减去除数* 2和除数* 3（同时在三个加法器上），然后我们将获得三位（结果的符号）信息，这些信息采用4个不同的值，因此您可以一次从它们中提取2位结果。 接下来，我们针对结果的3.4.5位外推类似的方法。
为了每个周期获得5位信息，我们需要31个加法器，每个加法器将执行分频除数* n（1-31）操作，结果的符号通过编码器传递，我们将立即接收5位结果。 然后我们将股息向左移动5位，并重复直到准备好。 然后我们需要32/5 = 6.4 => 7个措施来完成操作。
对于工作，我们需要31 + x加法器，这似乎很多，但我们已经有了它们，因为每个周期我们有32 * 32乘法运算，要实现它，我们就不能没有32加法器（嗯，我想是... ），这样我们已经有了必要的设备，唯一的问题是建立一个控制电路和一堆多路复用器以实现快速转换，但这是完全可以解决的。
因此，解决了分为7个步骤的任务，问题仍然存在-如何减少该时间，因为在所研究的MK中小于7。显而易见的解决方案是在算法准备阶段确定除数（H）和除数（3）的最高有效位数可以立即清楚地知道商的多少个高位等于零，因此我们可以跳过算法的前几个阶段。 例如，如果C <3，则结果立即为零，并且我们完成了运算，可以肯定的是，您可以导出度量数量的公式，但是我已经很无聊了。
有趣的是，尽管余数显然保留在内部的某个位置，但udiv操作仅给出商。 原则上，分两步获得它并不困难，这是通过执行伪代码Divisible-Private * Divider在机器代码的研究片段中完成的，但这是任何两步的，为什么不立即在寄存器对中给出它-我不知道答案一个问题。
总的来说，达到GDP，告诉他，如果他仍然感兴趣的话，我们一定会在MK中进行划分。
PS：顺便说一句，当我在寻找KDPV时（正如您所注意到的，我没有找到它），我注意到一个刻有错误的题词：“您不能被零除”。 我必须确定地说，可以除以零，不能除。 但是严重的是，在不同的体系结构中，它们除以零的方式不同，在x86中我们得到一个异常（这是一个令人难忘的错误200），在某些情况下我们得到了除数或零，但是我从未见过最大整数。 在ARM中，n / 0 = 0/0，结果为0。