Fast method for testing a bit of a large int

Question

In a number-theoretic algorithm manipulating very large integer n (hundred thousand bits to few millions), I need to test the j^th bit. Either of these work:

if 1<<j & n != 0 :
    # bit j of n is set

if n>>j & 1 != 0 :
    # bit j of n is set

but the duration of the test grows linearly with n.bit_length() (for j half that). Otherwise said per big-O notation, time is O(log(n)), when that could be O(1).

Is there an O(1) idiom to test a bit of an int in Python 3(.8), like we have mpz_tstbit() in GMP?

If not, where is the drop box for Python suggestions?

---

Addition per comment: n.bit_length() is at most 1<<24, with j < n.bit_length() and j>=0.

Answer 1

Disclaimer: I maintain gmpy2.

gmpy2 supports bit access in a few different ways. The gmpy2.bit_test(n,j) will test the j-th bit of n. n can be either a Python integer or a gmpy2 integer type.

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

The gmpy2.mpz integer type support a bit_test method. Other methods are also supported.

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

gmpy2.xmpz is a mutable integer type that supports bit access, including setting bits and accessing slices of bits.

>>> 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)

You can use xmpz integers in normal math operations. If you only use immediate operations (+=, *=, etc.), then the xmpz object will be updated in-place.

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

xmpz integers are a little strange at times, but they usually are very fast for direct bit access.