整数除法在python中是如何工作的？

Question

所以，我最近听说了整数除法，它非常快。当我做地板（x/2^n）时，我总是使用位移位

所以，我已经测试了哪一个是更快的整数除法或位移位，所以我制作了这段代码，它测试并比较了100次，然后找到了平均值：

    import timeit
    import statistics as stat
    
    def compare_times(a, b):
        res_a = timeit.timeit(a)
        res_b = timeit.timeit(b)
        c = res_a - res_b # if negative, a is faster 
        return c
    
    output = []
    
    for _ in range(100):
        output.append(compare_times("5 >> 1", "5 // 2"))
    
    print (stat.mean(output))

结果是肯定的，这意味着b更快。位移位不是直接在数字位工作吗？为什么它比整数除法慢

我测试了另一个东西，看看是否是因为我选择了5，所以：

    import timeit
    import statistics as stat
    import random
    
    def compare_times(a, b):
        res_a = timeit.timeit(a)
        res_b = timeit.timeit(b)
        c = res_a - res_b # if negative, a is faster 
        return c
    
    output = []
    
    for _ in range(100):
        number = random.randrange(5000, 50001)
        output.append(compare_times(f"{number} >> 1", f"{number} // 2"))
    
    print (stat.mean(output))

这也输出了正数

我唯一一次看到（位移位）比整数除法快的是在地板上（x/2^n），n>；=2.

那么，最终，整数除法是如何工作的呢？就较小的数字而言，为什么它比位移位更快

Answer 1

你看到的任何时差都是假的；实际上，5 // 2和5 >> 1都编译成相同的CPython字节码：

>>> from dis import dis
>>> dis('5 // 2')
  1           0 LOAD_CONST               2 (2)
              2 RETURN_VALUE
>>> dis('5 >> 1')
  1           0 LOAD_CONST               2 (2)
              2 RETURN_VALUE

也就是说，计算是在编译时完成的，而不是在运行时，所以实际上您只是在测量在这两种情况下加载预计算常量所需的时间。要获得准确的基准，您需要在运行时实际执行计算，例如通过传递变量；我还建议使用更大的数字（或将重复次数提高到默认值1000000以上），以获得更可靠的比较

>>> n = 1234 ** 56 # a 174-digit number
>>> from timeit import timeit
>>> timeit(lambda: n // 2)
0.32904140199389076
>>> timeit(lambda: n >> 1)
0.12879745499958517

所以我们可以看到，至少对于非常大的数字来说，正如您所期望的，位移动更快。对于较小的数字，可能没有显著差异

至于CPython实际上是如何计算整数除法的，可以免费阅读source code on GitHub，根据那里的评论，使用的算法可以在一本著名的教科书中找到：

    /* We follow Knuth [The Art of Computer Programming, Vol. 2 (3rd
       edn.), section 4.3.1, Algorithm D], except that we don't explicitly
       handle the special case when the initial estimate q for a quotient
       digit is >= PyLong_BASE: the max value for q is PyLong_BASE+1, and
       that won't overflow a digit. */