用于测试大整数的快速方法

Question

在处理非常大的整数n（数千位）的数论算法中，我需要测试j ^th位。这些工作之一：

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()线性增长。

[Python 3（.8）中是否有更有效的习惯用法，就像我们在GMP中使用mpz_tstbit()？

如果没有，Python建议的下拉框在哪里？

Answer 1

如果您的“ j”是固定的，则可以使用文字形式而不是使用“ j”来拼写数字-Python的编译器随后会记录“ 1 << j”作为文字，并且您将执行一个操作而不是两个操作。 （也就是说，如果“ j”不是变量，并且始终为“ 10204”，则应输入1 << 10204）

话虽如此，我认为您正在想象这种算法的运行方式是“将1千个比特一次一个地向左推”-不会发生这种情况。

用于大整数的算法可能会极大地优化“ 1 << j”整数的创建-尽管& n的结果将是“线性的”，但仍将是一个非常快速的操作。

总而言之，如果在运行后，应用程序的配置文件显示此操作的速度变慢，则可以使用大整数库，其性能可能比Python的本机整数高出一个数量级。

[过去，我曾经使用过GMP2 libray-可作为gmpy2应用于Python，并获得了不错的结果。\

关于您问题的细节，关于试图通过编写其他用于位测试的表达式来加快速度：这绝对是错误的方法-

如果Python中的数字变慢了[[too，并且更快的数字库根本不支持位测试，那么您可以推出自己的整数类型，该类型将存储错误号”在一个字节数组中，每个字节有8位，并为这些数字编写一个自定义的“位比较”方法。

相对于使用普通按位&进行测试所获得的加速是，您的函数将事先知道它必须与一个操作数上的一位匹配，而不必搜索其他“ 1”位在另一个操作数中-因此该操作将为O（1）。

但是我敢打赌，从中获得的提速将太少了-请记住，“过早的优化是万恶之源”。