为何两种近乎等效的PowerOfFour Python实现效率差异显著？

两段实现代码 #

实现一（耗时43ms，击败58%） #

import math

def isPowerOfFour(self, n: int) -> bool:
    if n <= 0:
        return False
    if math.log(n,4) - int(math.log(n,4)) !=0:
        return False
    else:
        return True

实现二（耗时56ms，击败11%） #

import math

def isPowerOfFour(self, n: int) -> bool:
    if n <= 0:
        return False
    nv = math.log(n,4) 
    if nv - int(nv) !=0:
        return False
    else:
        return True

核心疑问解析 #

你提到的“变量赋值比两次计算对数更耗时”显然不符合常理，实际出现这种反直觉结果，主要有这几个原因：

• LeetCode计时的随机性：平台的执行时间受服务器负载、测试用例执行顺序等多种外部因素影响，单次提交的时间参考性有限。同一代码多提交几次，可能会出现实现二比实现一更快的情况，不要过度纠结单次的百分比。
• Python解释器的细微优化：虽然理论上实现二只计算一次对数更高效，但Python的内置函数math.log可能对重复调用的相同参数有临时缓存，第二次调用直接取缓存结果，开销甚至比“赋值变量+读取变量”的组合更小。
• 浮点数运算的隐性差异：两次计算math.log(n,4)的结果可能因为浮点精度的微小波动，导致分支判断的执行路径和单次计算有细微差别（比如某些测试用例中，两次计算的差值刚好触发不同的分支预测），不过这种影响非常小。

额外提醒：浮点数实现的潜在问题 #

这两段代码都有一个致命缺陷：浮点数精度误差。比如当n是极大的4的幂时，math.log(n,4)可能因浮点精度限制，得到一个接近整数但并非严格整数的结果（比如4^20可能被计算为20.000000000000004），导致误判。

更可靠高效的实现是用位运算：

def isPowerOfFour(self, n: int) -> bool:
    # 首先是正整数，且是2的幂（n&n-1==0），然后1的位置在奇数位（和0x55555555按位与不为0）
    return n > 0 and (n & (n - 1)) == 0 and (n & 0x55555555) != 0

内容的提问来源于stack exchange，提问作者nzx0