使用逐位操作而不是测试偶数/奇数

Question

我试图理解这个素数分解的特殊解决方案（取自http://rosettacode.org/wiki/Prime_decomposition#Python:_Using_floating_point），我对step定义中位运算符的用法有点困惑

def fac(n):
    step = lambda x: 1 + (x<<2) - ((x>>1)<<1)
    maxq = long(floor(sqrt(n)))
    d = 1
    q = n % 2 == 0 and 2 or 3 
    while q <= maxq and n % q != 0:
        q = step(d)
        d += 1
    return q <= maxq and [q] + fac(n//q) or [n]

我理解它的作用（乘以x3，如果x是偶数，则加1，如果x是奇数，则加2），但son不太明白在这种情况下为什么要使用位操作。除了这个公式明显简洁之外，是否有理由使用位运算符而不是更明确的解决方案：

^{pr2}$

如果有一个很好的理由（比如说，(x>>1)<<1比模运算更有效，正如here）所建议的那样，是否有一种从具有多个按位运算符的表达式中提取底层逻辑的通用策略？在

---

更新

根据答案中的建议，我用步骤和步骤对版本进行计时，两者之间的差异是不可察觉的：

 %timeit fac(600851475143)
1000 loops, best of 3: 306 µs per loop

%timeit fac2(600851475143)
1000 loops, best of 3: 307 µs per loop

Answer 1

理论上，三位移位比一次乘法和一次除法更有效。在实践中，应该对这样的代码进行分析，以确保结果优化提供了足够的速度提升，以证明可读性的损失是合理的。在

任何使用这种优化的代码都应该清楚地记录代码的作用以及为什么优化被认为是有用的，如果只是为了将来的维护人员着想，他们可能会想用更可读的代码替换代码。在

Answer 2

这可能是对branch misprediction进行优化的尝试。现代的CPU是大规模流水线的；它们可以预先执行10条或更多条指令。一个近乎随机的有条件的分支有一半的时间是单向的，而另一半的时间则意味着CPU将不得不在一半的时间内抛出10条指令，这使得你的工作速度慢了5倍。至少在CPython中，分支预测失误的大部分成本都隐藏在开销中，但是您仍然可以很容易地发现它们至少会增加12%的时间，如果不是C中预期的500%

另一种选择是，作者正在优化一些更不相关的东西。在70年代和80年代的硬件上，用位操作代替算术运算通常会导致巨大的加速，这是因为算术逻辑单元很简单，而且编译器没有进行太多优化。即使是那些实际上不希望得到同样的加速的人，也已经将所有标准的玩弄技巧内化了，不用想就可以使用它们。（或者，当然，作者可能只是从C、Scheme或其他语言移植了一些代码，而这些代码可能是几十年前编写的，当时这种优化产生了巨大的影响。）

无论如何，这段代码几乎肯定是在错误的地方进行了优化。定义一个在内部循环中每次调用的函数，而不是只在那里内联一行表达式，增加的开销远远超过12%。代码使用step = lambda x: …而不是def step(x): …这一事实强烈地表明作者对Python并不熟悉，也不知道如何对其进行优化。如果您真的想让它更快地运行，几乎可以肯定的是，有很多事情会比您为step使用的实现产生更大的差异。在

也就是说，对于任何你不确定的优化，正确的做法就是测试它。两种方法都可以实现，使用timeit来查看差异，如果不理解结果，可以使用Python级别的探查器或硬件级别的性能计数器（例如，通过cachegrind）或其他方法来获取更多信息。通过对原始代码的快速测试，使用IPython的%timeit对原始代码进行了各种各样的测试，得到的结果从.92x到1.08x倍不等。换句话说，这似乎是一场洗礼