一种快速测试大整数某一位的方法

Question

在一个处理非常大的整数n（几十万到几百万位）的数论算法中，我需要测试第j位。以下两种方法都可以：

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。

- fgrieu

---

这种位操作通常用于节省内存。你有很多这样的整数吗？一个简单的布尔列表可能更有用：if n[j]: ...。 - chepner

话虽如此，在担心当前的方法是否足够快之前，您应该对代码进行分析。 - chepner

一种了解Python整数内部结构的C函数几乎肯定可以更快地执行此测试，但我怀疑这样的函数是否已经存在。 - Mark Ransom

如果您想要这样的功能，最好直接使用GMP。有Python绑定可用。 - user2357112

Python在内部以30位（在32位整数中）的“块”形式存储大整数，因此它可以通过执行不会溢出的数学运算来模拟进位传播。我不知道是否有一种方法在Python中索引一个块。 - Peter Cordes

Answer 1

声明：我维护 gmpy2。

gmpy2 支持几种不同的位访问方式。使用gmpy2.bit_test(n,j) 可以测试第 j 位的 n 。n 可以是 Python 整数或 gmpy2 整数类型。

>>> gmpy2.bit_test(78,2)
True

整数类型支持方法。还支持其他方法。

>>> a=gmpy2.mpz(123456)
>>> a.bit_test(27)
False

gmpy2.xmpz 是一种可变整数类型，支持位访问，包括设置位和访问位的切片。

>>> a=gmpy2.xmpz(123456)
>>> a[27]
0
>>> a[27]=1
>>> a[27]
1
>>> a[27:30]
mpz(1)
>>> a[27:30] = -1
>>> a[27:30]
mpz(7)

在普通的数学运算中，您可以使用 xmpz 整数。如果只使用即时操作（+=，*=等），那么 xmpz 对象将在原地更新。

>>> a
xmpz(939647552)
>>> b=a
>>> a+=9999
>>> a
xmpz(939657551)
>>> b
xmpz(939657551)

xmpz 整数有时可能有些奇怪，但通常对于直接位访问非常快。

- casevh

---

pip3 install https://download.lfd.uci.edu/pythonlibs/g5apjq5m/gmpy2-2.0.8-cp38-cp38-win_amd64.whl，我在Python 3.8中使用方便的包装类拥有了gmp！！对于其他版本的Python，请使用Christoph Gohlke的存储库中适当的whl文件。也可以提供先前下载文件的路径。 - fgrieu

Answer 2

如果您的“j”是固定的，您可以用文字形式拼写数字，而不是使用“j”——Python的编译器会将“1 << j”记录为文字，这样您就只需要一个操作，而不是两个。（也就是说，如果“j”不是变量，而总是，比如“10204”，那么您应该写1 << 10204）

话虽如此，我认为您想象的算法运行方式是“平静地一位一位地将1向左移”，但实际情况并非如此。

对于大整数，算法很可能会优化创建“1 << j”整数的过程，而尽管& n的结果将是“线性的”，但它仍然是一个非常快速的操作。

总之，如果在运行后，您的应用程序配置文件显示这个操作有减速，那么有一些大整数库可以比Python的本机整数快一个数量级以上。

过去我使用过GMP2库——作为Python的gmpy2，并取得了良好的结果。

至于您问题的具体内容，即通过编写其他表达式来加速位测试：这绝对是错误的方法。

如果Python中的数字速度太慢，并且更快的数字库根本不支持位测试，那么您可以自己编写整数类型，将大数字存储在一个bytearray中，每个字节有8位，并为这些数字编写一个自定义的“比特比较”方法。

相对于使用常规的按位&进行测试，您将获得的加速效果是，您的函数事先就知道它必须匹配操作数中的单个位，而不必在另一个操作数中搜索其他“1”位——因此操作的时间复杂度将是O（1）。

但我敢打赌，这样做所获得的加速效果太小了——请记住，“过早优化是万恶之源”。 更新：gmp在构建1 << j数字方面并不更快：

In [22]: a = bmpy2.numer(1); b = gmpy2.numer(10_000_000)                                                                                                   

In [23]: %timeit a << b                                                                                                                
25.8 µs ± 508 ns per loop (mean ± std. dev. of 7 runs, 10000 loops each)

In [24]: %timeit 1 << 10_000_000                                                                                                       
27.2 µs ± 239 ns per loop (mean ± std. dev. of 7 runs, 10000 loops each)

- jsbueno

---

不，我并没有想象它将1向左移动j次，这将花费O(j^2)，因此最终为O(Log(n)^2)。我想象（并且非常自信）成本是O(Log(n))，当它可以是O(1)时。gmpy2可能是一个好主意，但它并不完全是Python习语。 - fgrieu

我进行了一些使用 2 ** j 而不是 1 << j 的 "timeit" 测试，结果速度慢了整整 1000 倍。显然，Python 的编译/解析时间优化中还有改善的空间。 - jsbueno

即使某些静态类型分析可以确定j将是一个整数，我们仍然需要知道j是非负的，才能用1<<j替换2**j，这并不容易（Python甚至没有无符号整数）。这可能与为什么2**j较慢有关。 - fgrieu

我得出结论，没有内置的惯用语（除了也许是将int的内部表示索引为hinted，这会牺牲清晰度和与可能的演变的兼容性）。我接受智慧（在两个 评论中获得认同），如果性能至关重要，则使用GMP绑定是正确的选择。这确实可以加速算法的其他部分。可惜必须在速度和简洁+清晰之间做出选择。 - fgrieu

你并没有提及其他的限制条件 - 但一个相对简单的方法是继承 "int"，在其 __new__ 上返回将其纯字节表示存储在属性中 - (int.to_bytes 方法)，并有一个检查单个设置位的方法，通过查看这个字节数组可以实现 O(1)。显然，这样做会带来空间和处理方面的开销，但它们只需要为每个大整数支付一次。 - jsbueno