在一个处理非常大的整数n(几十万到几百万位)的数论算法中,我需要测试第j位。以下两种方法都可以:
但是测试的持续时间与
在Python 3(.8)中,是否有一种O(1)的惯用法来测试
如果没有,那么Python建议箱在哪里?
if 1<<j & n != 0 :
# bit j of n is set
if n>>j & 1 != 0 :
# bit j of n is set
但是测试的持续时间与
n.bit_length()
成线性增长(对于j
是一半)。换句话说,根据big-O notation,时间复杂度为O(log(n
)),而实际上可以是O(1)。在Python 3(.8)中,是否有一种O(1)的惯用法来测试
int
的位,就像我们在GMP中有mpz_tstbit()
一样?如果没有,那么Python建议箱在哪里?
每评论增加一次: n.bit_length()
最多为 1<<24
,其中 j < n.bit_length()
并且 j>=0
。
if n[j]: ...
。 - chepner