擅长:python、mysql、java
<p>我想知道这段代码:</p>
<pre><code># factor n - 1 as 2^(r)*s
while r % 2 == 0:
s = s + 1
r = r // 2 # floor
</code></pre>
<p>让我们拿<code>n = 7</code>。所以<code>n - 1 = 6</code>。我们可以把<code>n - 1</code>表达为<code>2^1 * 3</code>。在这种情况下,<code>r = 1</code>和<code>s = 3</code>。</p>
<p>但是上面的代码发现了一些别的东西。它以<code>r = 6</code>开头,所以<code>r % 2 == 0</code>。最初,<code>s = 0</code>因此在一次迭代之后,我们有<code>s = 1</code>和<code>r = 3</code>。但现在<code>r % 2 != 0</code>循环终止。</p>
<p>我们最终得到了<code>s = 1</code>和<code>r = 3</code>,这显然是不正确的:<code>2^r * s = 8</code>。</p>
<p>不应在循环中更新<code>s</code>。相反,您应该计算可以被2除多少次(这将是<code>r</code>),除后的结果将是<code>s</code>。在<code>n = 7</code>,<code>n - 1 = 6</code>的例子中,我们可以将它划分一次(所以<code>r = 1</code>),然后在划分之后,我们得到3(所以<code>s = 3</code>)。</p>