3

大家好，我正在尝试仅使用移位和加/减来除以无符号常数 - 如果它是乘法，我对此没有任何问题，但我对除法有点难过。

例如，假设常数除数是 192，假设除数是 8000

“完整结果” y = 8000/192 = 41（假设我不保留小数位）

y = 8000 >> 8 ... 31 y = 8000 >> 7 ... 62

但是如何获得更准确的解决方案？

非常感谢！

4

3 回答 3

9

几乎可以肯定有一种更优雅的方法可以做到这一点，但这足以让您入门。

通常这种方式的除法是通过乘以倒数来完成的，即先乘法然后右移。

（注意：请记住，乘法可以通过移位和加法来完成（例如n * 3 = (n*2) + (n*1) = (n << 1) + (n) )，但我只是在这里使用乘法。你的问题是“移位和加法”，我正在证明我使用乘法的速记）

在下面的例子中，我试图用一个例子来解释这些概念。在您的具体情况下，您需要考虑诸如

  1. 符号（我在下面使用无符号整数）

  2. 溢出（下面我使用 32 位无符号长整数来保存中间值，但如果您使用的是较小的 uC，请注意，请进行相应调整

  3. 四舍五入（例如 9/5 应该返回 1 还是 2？在 C 中，它是 1，但也许你想要 2，因为它更接近正确答案？）

  4. 在您可以（可用位）的范围内，在除法之前进行所有乘法运算（最大限度地减少截断错误）。再次，注意溢出。

正如我所说，请阅读以下内容以了解这些概念，然后根据您的需求进行定制。

除以 192 与乘以 1/192 相同，与除以 (64 * 3) 相同。1/3 没有精确的（有限）二进制表示，所以我们用 0x5555/(1 << 16) 来近似它。

要除以 192，我们先除以 64，然后再除以 3。要除以 3，我们乘以 0x5555 并右移 16（或乘以 0x55 和 >> 8，或者...）

//                8000/192          =
//                ((8000/64)/3)     =
//                ((8000 >> 6) / 3) =
//                (((8000 >> 6) * 0x5555) >> 16)
//                (((8000 * 0x5555) >> 22

请注意，括号是故意的。您不想计算(8000 * (0x5555/(1 << 16))，因为第二项为 0，而乘积将为 0。不好。

因此，代码中的 1-liner 将类似于：

 printf("Answer:  %lu\n", ((8000UL * 0x5555UL) >> 22));

这将产生 41，这是“C”将产生的结果8000/192，即使 42 “更接近”。通过检查 LSB，您可以根据需要进行舍入。

有人可以写一篇关于这个主题的论文，但幸运的是，比我聪明得多的人已经有了。

于 2011-02-03T20:24:51.597 回答
5

我开发了一个常数除法生成器，它可以很容易地为您提供任何常数的优化除法。它遵循“Hacker's Delight”的想法。

sourceforge 提供了名为“kdiv”的工具：

http://sourceforge.net/projects/kdiv/

于 2011-08-07T23:00:34.693 回答
2

对于这类事情，我会看黑客的喜悦书。我没有我的副本，但是如果您查看除数 192，即 0xC0，则与此无关，因此您可以将顶部和底部除以 0x40，移位 8000>>6 = 125. 8000/192 -> 125/ 3，但是你必须除以 3。我们知道答案将在 125/2 和 125/4 之间。使用这些特定数字，125 是 0x7d 或 b1111101 是 b100000 + 11101 的 3 倍，即 (3 乘以 0x20) + (3 乘以 8) + 5 所以 125/3 = 0x20 + 0x8 + (5/3) 和 5/3 是很快确定为大于 1 但小于 2，因此 0x28+1 = 41。如果除数位模式不断出现在分子位模式的高位上，则仅随着移位继续减少。我不知道黑客对此事感到高兴或其他类似消息来源怎么说，

于 2011-02-03T16:09:24.923 回答