用一个常数司通过移位，并添加/减去 [英] Division by a constant using shifts and adds/subtracts
问题描述
大家好我试图用一个无符号常量来划分只用移位和加法/减 - 我有这个没有问题，如果它是乘法，但我是一个有点分裂难倒。
Hi all I'm trying to divide by an unsigned constant using only shifts and adds/subtracts - I have no problem with this if it were multiplication, but I'm a bit stumped by the division.
举例来说，可以说不断的除数是192和让说，分红为8000
For example, lets say the constant divisor is 192 and lets say the dividend is 8000
完整的结果Y =192分之8000= 41（假定我没打扰小数位）
"full result" y = 8000/192 = 41 (assuming I'm not keeping fractional bits)
Y = 8000 >> 8 ... 31
Y = 8000 >> 7 ... 62
y = 8000 >> 8 ... 31 y = 8000 >> 7 ... 62
但我怎么得到更准确的解决方案？
But how do I get a more accurate solution?
非常感谢！
推荐答案
有几乎可以肯定是一个更优雅的方式做到这一点，但这里有足够让你开始。
There is almost certainly a more elegant way to do it, but here's enough to get you started.
在这种方式通常划分由倒数相乘，即第一乘以做到，那么右移。
Usually division in this way is done by multiplying by the reciprocal, i.e., first multiplying and then right-shifting.
（注意：请记住，multplication可以通过转移来完成，并添加（如 N * 3 =（N * 2）+（N * 1）=（N＆LT;＆LT; 1）+（ N）），但我只是在这里用乘法你的问题说，转变＆安培;增加了，我证明我的速记使用乘法）
(Note: remember that multplication can be accomplished by shifts and adds (e.g. n * 3 = (n*2) + (n*1) = (n << 1) + (n) ) but I'm just going to use multiplication here. Your question said "shifts & adds" and I'm justifying my shorthand use of multiplication)
在下面的例子中，我试图用一个例子来解释概念。在特定的情况下，你要考虑，如
In the examples below, I'm trying to explain the concepts with an example. In your specific case, you'll want to consider issues such as
-
标志（我用下面的无符号整数）
sign (I'm using unsigned ints below)
溢出（下面我使用的是32位无符号多头持有中间值，但如果你是在一个较小的uC提防，相应地调整
overflow (below I'm using 32-bit unsigned longs to hold intermediate values but if you're on a smaller uC beware, adjust accordingly
四舍五入（例如应归还9/5 1或2？在C，这是1，但也许你想2，因为它更接近正确答案？）
rounding (e.g. should 9/5 return 1 or 2? In C, it's 1, but maybe you want 2 because it's closer to the correct answer?)
在某种程度上，你可以（可用位），你的鸿沟（减少截断误差）之前，做你所有的成倍增加。再次，要注意溢出。
To the extent that you can (available bits), do your all of your multiplies before your divides (minimizing truncation errors). Again, be aware of overflow.
正如我所说，阅读下面的理解概念，然后量身定制您的需求。
As I said, read the below to understand the concepts, then tailor to your needs.
由192除以相同由1/192相乘，这是相同的由（64 * 3）分裂。没有一个确切的（有限）的二进制重新$ P $的1/3 psentation，所以我们用0x5555加/（1 LT;＆LT; 16）接近它。
Dividing by 192 is the same as multiplying by 1/192, which is the same as dividing by (64 * 3). There is not an exact (finite) binary representation of 1/3, so we're approximating it with 0x5555/(1 << 16).
要192分，我们把64再由3鸿沟除以3，我们通过将0x5555繁殖和16右移（或0x55和乘>> 8，或......）
To divide by 192, we divide by 64 and then divide by 3. To divide by 3, we multiply by 0x5555 and shift right by 16 (or multiply by 0x55 and >> 8, or...)
// 8000/192 =
// ((8000/64)/3) =
// ((8000 >> 6) / 3) =
// (((8000 >> 6) * 0x5555) >> 16)
// (((8000 * 0x5555) >> 22
请注意，括号是故意的。您不要计算（8000 *（0x5555加/（1 LT;＆LT; 16）），因为第二项为0，该产品将是0不好。
Please note that the parentheses are intentional. You don't want to compute (8000 * (0x5555/(1 << 16)) because the 2nd term is 0, and the product would be 0. Not good.
因此，一个1班轮在code会是这样的：
So a 1-liner in code would be something like:
printf("Answer: %lu\n", ((8000UL * 0x5555UL) >> 22));
这将产生41，这就是所谓的C将产生的192分之8000，即使42更接近。通过检查LSB的，如果你想，你可以圆。
This will yield 41, which is what "C" would yield for 8000/192, even though 42 is "closer". By checking LSBs you could round if you wanted to.
，可以写关于这个主题的论文，但比我还好的 别人更聪明已经有
One could write a treatise on this topic, but fortunately someone much smarter than me already has.
这篇关于用一个常数司通过移位，并添加/减去的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
