定点码分理解

Question

定点除以9的代码。

  1. q = 0;              // quotient
  2. y = (x << 3) - x;   // y = x * 7
  3. while(y) {          // until nothing significant
  4.   q += y;           // add (effectively) binary 0.000111
  5.   y >>= 6;          // realign
  6. }
  7. q >>= 6;            // align

while loop 的第一次执行中的第 2 行到第 5 行有效
x*.000111 (in decimal representation x*0.1)，它在后续的while loops中试图达到什么目的？

难道不应该再次将其乘以 7 并再次移位吗只做转移以照顾复发？

关于纯十进制数乘法的解释，即仅通过移位实现的结果会很好。

详细代码解释在这里：

Answer 1

左移一位乘以二，右移一位除以二。为什么？

移位是从您的号码中取出所有位并将它们 n 位移动到 left/right 的操作。例如：

00101010 is 42 in Binary
42 << 2 means "shift 42 2 bits to the left" the result is
10101000 which is 168 in Binary
we multiplied 42 by 4.

42 >> 2 means "shift 42 2 bits to the right" the result is
00001010 which is 10 in binary (Notice the rightmost bits have been discarded)
we divided 42 by 4.

类似地：(x << 3) 是 x * 8，所以 (x << 3) - x 是 (x * 8) - x => x * 7

Answer 2

让我们用字母 F 表示 7/64。 7/64 在二进制中表示为 0.000111，非常接近 1/9。但非常接近是不够的。我们想用 F 精确到 1/9。它是通过以下方式完成的

F+ (F/64) + (F/64^2) + (F/64^3) + (F/64^4)+ (F/64^5) + ...

随着我们向这个序列中添加更多元素，结果越来越接近 1/9 请注意，序列中的每个元素与前一个元素完全 1/64。

除以 64 的快速方法是 >>6

您实际上想要构建一个循环来对这个序列求和。您从 F 开始，在每次迭代中执行 F>>6 并将其添加到总和中。最终（经过足够的迭代）总和将正好是 1/9.

现在好了，你已经准备好理解代码了。代码没有使用 F（这是一个分数，不能用定点表示），而是将 F 乘以 x。所以序列的总和将是 X/9 而不是 1/9 此外，为了使用固定点，最好存储 64*X*F，结果将是 64*X/9.

求和后我们可以除以 64 得到 X/9

代码将F*x*64

的值存储在变量y中

变量q存储序列的和。在每次循环迭代中，我们通过将前一个元素除以 64 (y>>=6)

来生成序列中的下一个元素

最后在循环之后我们将总和除以 64 (q>>=6) 得到结果 X/9.

关于你的问题。不能每次都乘以7，否则会得到

序列的和

F+ (F^2) + (F^3) + (F^4) + (F^5)...

这将产生 ~X/(8+1/7) 而不是 X/9 的结果。

定点码分理解

Fixed point code division understanding

c

algorithm

math

fixed-point