Dear comp.lang.python,

When I asked ChatGPT how I would get the number of zero bits in a Python integer, it spouted some nonsense about calculating it with

( n & -n ).bit_length() - 1

but that hardly seems like the best way. Specifically, I'm trying to
count the number of zero bits to the right of the rightmost one bit.

The above formula seems to work, given a few spot checks, but I thought
this should be a utility function in the underlying multiprecision lib-
rary in Python. Is the calculation n & -n really necessary?


What does the Lawrence D'Oliveiro say about this?
--
Johann | email: invalid -> com | http://www.myrkraverk.com/blog/
I'm not from the Internet, I just work there. | via Easynews.com https://bsky.app/profile/myrkraverk.bsky.social | for ( ;; ) _:;


--- PyGate Linux v1.5.19
* Origin: Dragon's Lair, PyGate NNTP<>Fido Gate (3:633/10)

On 9/20/2026 2:23 AM, Stefan Ram wrote:

"Johann \"Myrkraverk\" Oskarsson" <johann@myrkraverk.invalid> wrote or quoted:

The above formula seems to work, given a few spot checks, but I thought
this should be a utility function in the underlying multiprecision lib-
rary in Python. Is the calculation n & -n really necessary?

While "n & -n" might take some time for large Python integers,
I see no way to do it faster in Python.

In C, one might be able to access the segments of large numbers
(the "limbs") starting with the least significant one to shortcut
the operation as soon as a "1" is found.

Yes, this is perplexing. I'm working with /arbitrary large numbers/ in Cryptohack, for cryptographic purposes, and need a utility function to
count the number of zero bits from the right.

The toy implementations of the Jacobi Symbol I've seen online, in Python
and otherwise, all seem to use a loop to repeatedly divide by two, which
is presumably much slower, so I'm /sort of happy/ with this method.

For practical applications, I resorted to the jacobi_symbol() function
in SymPy, since I have not finished a correct implementation myself.
But more on that in a later post.
--
Johann | email: invalid -> com | http://www.myrkraverk.com/blog/
I'm not from the Internet, I just work there. | via Easynews.com https://bsky.app/profile/myrkraverk.bsky.social | for ( ;; ) _:;

--- PyGate Linux v1.5.19
* Origin: Dragon's Lair, PyGate NNTP<>Fido Gate (3:633/10)

Johann "Myrkraverk" Oskarsson wrote:

On 9/20/2026 2:23 AM, Stefan Ram wrote:

"Johann \"Myrkraverk\" Oskarsson" <johann@myrkraverk.invalid> wrote or
quoted:

The above formula seems to work, given a few spot checks, but I thought
this should be a utility function in the underlying multiprecision lib-
rary in Python.ÿ Is the calculation n & -n really necessary?

ÿÿ While "n & -n" might take some time for large Python integers,
ÿÿ I see no way to do it faster in Python.

ÿÿ In C, one might be able to access the segments of large numbers
ÿÿ (the "limbs") starting with the least significant one to shortcut
ÿÿ the operation as soon as a "1" is found.

Yes, this is perplexing.ÿ I'm working with /arbitrary large numbers/ in Cryptohack, for cryptographic purposes, and need a utility function to
count the number of zero bits from the right.

The toy implementations of the Jacobi Symbol I've seen online, in Python
and otherwise, all seem to use a loop to repeatedly divide by two, which
is presumably much slower, so I'm /sort of happy/ with this method.

For practical applications, I resorted to the jacobi_symbol() function
in SymPy, since I have not finished a correct implementation myself.
But more on that in a later post.

Negative values are stored by flipping all bits of n and adding 1. This
is exactly why negating numbers with trailing zeros causes long carry
chains, and negating numbers with trailing ones does not.

--
Everything I fight for leaves a bitter taste
Everything I cry for laughs into my face
Everything I scream for barely knows my name
Everything I'd die for will die just the same

--- PyGate Linux v1.5.19
* Origin: Dragon's Lair, PyGate NNTP<>Fido Gate (3:633/10)

On 9/20/2026 3:37 AM, Lane W wrote:

Johann "Myrkraverk" Oskarsson wrote:

On 9/20/2026 2:23 AM, Stefan Ram wrote:

"Johann \"Myrkraverk\" Oskarsson" <johann@myrkraverk.invalid> wrote
or quoted:

The above formula seems to work, given a few spot checks, but I thought >>>> this should be a utility function in the underlying multiprecision lib- >>>> rary in Python.ÿ Is the calculation n & -n really necessary?

ÿÿ While "n & -n" might take some time for large Python integers,
ÿÿ I see no way to do it faster in Python.

ÿÿ In C, one might be able to access the segments of large numbers
ÿÿ (the "limbs") starting with the least significant one to shortcut
ÿÿ the operation as soon as a "1" is found.

Yes, this is perplexing.ÿ I'm working with /arbitrary large numbers/ in
Cryptohack, for cryptographic purposes, and need a utility function to
count the number of zero bits from the right.

The toy implementations of the Jacobi Symbol I've seen online, in Python
and otherwise, all seem to use a loop to repeatedly divide by two, which
is presumably much slower, so I'm /sort of happy/ with this method.

For practical applications, I resorted to the jacobi_symbol() function
in SymPy, since I have not finished a correct implementation myself.
But more on that in a later post.

Negative values are stored by flipping all bits of n and adding 1. This
is exactly why negating numbers with trailing zeros causes long carry chains, and negating numbers with trailing ones does not.

Thank you for that exposition. This is precisely why I am perplexed and befuddled. For arbitrary long integers -- in bits -- this chain of
carries over unknown machine words internally to the Python interpreter
seems completely unnecessary, and it really should be simpler to just
count the zero bits in the underlying C code.

Why can't we do that?
--
Johann | email: invalid -> com | http://www.myrkraverk.com/blog/
I'm not from the Internet, I just work there. | via Easynews.com https://bsky.app/profile/myrkraverk.bsky.social | for ( ;; ) _:;

--- PyGate Linux v1.5.19
* Origin: Dragon's Lair, PyGate NNTP<>Fido Gate (3:633/10)

On 9/20/2026 4:32 AM, Johann "Myrkraverk" Oskarsson wrote:

On 9/20/2026 3:37 AM, Lane W wrote:

Johann "Myrkraverk" Oskarsson wrote:

On 9/20/2026 2:23 AM, Stefan Ram wrote:

"Johann \"Myrkraverk\" Oskarsson" <johann@myrkraverk.invalid> wrote
or quoted:

The above formula seems to work, given a few spot checks, but I
thought
this should be a utility function in the underlying multiprecision
lib-
rary in Python.ÿ Is the calculation n & -n really necessary?

ÿÿ While "n & -n" might take some time for large Python integers,
ÿÿ I see no way to do it faster in Python.

ÿÿ In C, one might be able to access the segments of large numbers
ÿÿ (the "limbs") starting with the least significant one to shortcut
ÿÿ the operation as soon as a "1" is found.

Yes, this is perplexing.ÿ I'm working with /arbitrary large numbers/ in
Cryptohack, for cryptographic purposes, and need a utility function to
count the number of zero bits from the right.

The toy implementations of the Jacobi Symbol I've seen online, in Python >>> and otherwise, all seem to use a loop to repeatedly divide by two, which >>> is presumably much slower, so I'm /sort of happy/ with this method.

For practical applications, I resorted to the jacobi_symbol() function
in SymPy, since I have not finished a correct implementation myself.
But more on that in a later post.

Negative values are stored by flipping all bits of n and adding 1.
This is exactly why negating numbers with trailing zeros causes long
carry chains, and negating numbers with trailing ones does not.

Thank you for that exposition.ÿ This is precisely why I am perplexed and befuddled.ÿ For arbitrary long integers -- in bits -- this chain of
carries over unknown machine words internally to the Python interpreter
seems completely unnecessary, and it really should be simpler to just
count the zero bits in the underlying C code.

Why can't we do that?

For instance, here is the utility function in LibTomMath, mp_cnt_lsb(),
chosen because I was looking at the Jacobi Symbol algorithm in Tom St
Denis' book, /BigNum Math/ when I came across this little optimization.

https://github.com/libtom/libtommath/blob/develop/mp_cnt_lsb.c

I presume all erudite readers of comp.lang.python already have a physi-
cal copy on their shelf, but I can link the PDF in the GitHub assets if requested. Please turn to page 270, line 057 in the code listing.

I have added comp.lang.c, if anyone needs the standard thumpers to
explain the code in the link, and sci.math, if anyone needs an expla-
nation of the mathematics.

For the latter, I use /Graduate Texts in Mathematics #84/,

/A Classical Introduction to Modern Number Theory/

by Kenneth Ireland, and Michael Rosen. See

https://link.springer.com/series/0136

for the entire series. I do not use L.L.Ms. to grok mathematics.


So, presuming this is a standard function in all multiprecision arith-
metical libraries, why can't we just do this directly in Python?
--
Johann | email: invalid -> com | http://www.myrkraverk.com/blog/
I'm not from the Internet, I just work there. | via Easynews.com https://bsky.app/profile/myrkraverk.bsky.social | for ( ;; ) _:;

--- PyGate Linux v1.5.19
* Origin: Dragon's Lair, PyGate NNTP<>Fido Gate (3:633/10)

On 9/20/2026 4:39 AM, Stefan Ram wrote:

"Johann \"Myrkraverk\" Oskarsson" <johann@myrkraverk.invalid> wrote or quoted:

it really should be simpler to just
count the zero bits in the underlying C code.

Why can't we do that?

You /can/ ask your chatbot to generate a C extension that does this
and explain how to compile and call it from Python.

Thank you. I will try that in the near future. I put my Python/Crypto-
hack adventures on hold while reading some more on the mathematics, and
I found myself enjoying /Applied Cryptography/ by Schneier. You know,
the guy with the blog, and

https://www.schneierfacts.com/

so I suppose he is a cryptographic influencer of some kind.
--
Johann | email: invalid -> com | http://www.myrkraverk.com/blog/
I'm not from the Internet, I just work there. | via Easynews.com https://bsky.app/profile/myrkraverk.bsky.social | for ( ;; ) _:;

--- PyGate Linux v1.5.19
* Origin: Dragon's Lair, PyGate NNTP<>Fido Gate (3:633/10)

"Johann \"Myrkraverk\" Oskarsson" <johann@myrkraverk.invalid> writes:

( n & -n ).bit_length() - 1

This formula is very famous. In twos complement arithmetic, -n is (1
plus the bit complement of n_. So first, turn all the rightmost 0's
into 1's. The 1 immediately to the left of the rightmost 0 (call this
bit # k) turns into a 0. All the other bits are similarly inverted.

Now add 1. So the now-rightmost block of 1's turn back into 0. Bit # k
turns back into 1. And all the other bits stay inverted.

Now AND. All the upper bits are ANDed with their complements so they
become 0. Bit # k remains 1. And all the bits below it are 0. So
you've zeroed all the bits except the 1 immediately to the left of the
block of 0's that you're interested in. The bit length is the length of
(the block you want plus the leading 1). So subtract 1 to adjust for
the leading 1 being counted. Done.

--- PyGate Linux v1.5.19
* Origin: Dragon's Lair, PyGate NNTP<>Fido Gate (3:633/10)