Skip to main content
 首页 » 编程设计

python之使用按位运算而不是测试偶数/奇数

2025年05月04日11itcoder

我正在尝试了解这个素数分解的特定解决方案(取自 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] 

我明白它的作用(乘以 x 3,然后如果 x 是偶数则加 1,如果 x 是奇数则加 2),但我不太明白为什么要在这种情况下求助于按位运算。除了此公式明显的简洁性之外,是否还有理由使用按位运算符而不是更明确的解决方案:

mystep = lambda x: (3 * x) + 1 if (x % 2 == 0) else (3 * x) + 2 

如果有充分的理由(例如,(x>>1)<<1 比模运算更有效,如 here 所建议),是否有一种通用策略可以从具有多个按位运算符的表达式中提取底层逻辑?


更新

按照答案中的建议,我用step和我的step都对版本进行了计时,区别是难以察觉的:

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

请您参考如下方法:

这可能是围绕 branch misprediction 进行优化的尝试.现代 CPU 是大规模流水线的;他们推测性地提前执行了 10 条或更多指令。一个条件分支在一半时间里几乎随机地走一条路,一半时间里走另一条路,这意味着 CPU 将不得不在一半的时间里抛出 10 条指令的工作量,使你的工作速度减慢 5 倍。至少对于 CPython,分支预测错误的大部分成本都隐藏在开销中,但您仍然可以轻松找到它们将时间增加至少 12% 的情况,如果不是您在 C 中预期的 500% 的话。

另一种情况是,作者正在针对更不相关的内容进行优化。在 70 年代和 80 年代的硬件上,用按位运算代替算术运算通常会带来巨大的加速,这只是因为 ALU 很简单而且编译器没有进行太多优化。即使是那些实际上并不期望今天获得相同加速的人也已经内化了所有标准的位旋转黑客并且不假思索地使用它们。 (或者,当然,作者可能只是从 C 或 Scheme 或其他某种语言中移植了一些代码而没有真正考虑它,并且该代码可能是在几十年前编写的,当时这种优化产生了很大的不同。)

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

话虽如此,对于您不确定的任何优化,正确的做法是对其进行测试。以两种方式实现它,使用 timeit 来查看差异,如果您不理解结果,请使用 Python 级别的分析器或硬件级别的性能计数器(例如,通过 cachegrind) 或其他东西来获取更多信息。通过针对您的替代方案对原始代码进行非常快速的测试,使用 IPython 的 %timeit 向其输入各种数字,我得到的结果范围是您的版本的 0.92 倍到 1.08 倍的时间。换句话说,好像是洗...