Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.python > #198027

Re: ( n & -n ).bit_length() - 1 ## Really?

Cross-posted to 3 groups.

Show all headers | View raw

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 ( ;; ) _:;

Back to comp.lang.python | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

( n & -n ).bit_length() - 1 ## Really? "Johann \"Myrkraverk\" Oskarsson" <johann@myrkraverk.invalid> - 2026-09-20 01:56 +0800
  Re: ( n & -n ).bit_length() - 1 ## Really? ram@zedat.fu-berlin.de (Stefan Ram) - 2026-09-19 18:23 +0000
    Re: ( n & -n ).bit_length() - 1 ## Really? "Johann \"Myrkraverk\" Oskarsson" <johann@myrkraverk.invalid> - 2026-09-20 03:15 +0800
      Re: ( n & -n ).bit_length() - 1 ## Really? Lane W <cactus_DAC@yahoo.com> - 2026-09-19 13:37 -0600
        Re: ( n & -n ).bit_length() - 1 ## Really? "Johann \"Myrkraverk\" Oskarsson" <johann@myrkraverk.invalid> - 2026-09-20 04:32 +0800
          Re: ( n & -n ).bit_length() - 1 ## Really? ram@zedat.fu-berlin.de (Stefan Ram) - 2026-09-19 20:39 +0000
            Re: ( n & -n ).bit_length() - 1 ## Really? "Johann \"Myrkraverk\" Oskarsson" <johann@myrkraverk.invalid> - 2026-09-20 04:56 +0800
            myrkraverk.c (was: Re: ( n & -n ).bit_length() - 1 ## Really?) "Johann \"Myrkraverk\" Oskarsson" <johann@myrkraverk.invalid> - 2026-09-20 18:00 +0800
              Re: myrkraverk.c ram@zedat.fu-berlin.de (Stefan Ram) - 2026-09-20 12:25 +0000
                Re: myrkraverk.c "Johann \"Myrkraverk\" Oskarsson" <johann@myrkraverk.invalid> - 2026-09-20 21:33 +0800
                Re: myrkraverk.c ram@zedat.fu-berlin.de (Stefan Ram) - 2026-09-20 13:48 +0000
                Re: myrkraverk.c "Johann \"Myrkraverk\" Oskarsson" <johann@myrkraverk.invalid> - 2026-09-20 22:09 +0800
              jacobi_symbol.py (was: Re: myrkraverk.c) Johann 'Myrkraverk' Oskarsson <johann@myrkraverk.invalid> - 2026-09-21 20:34 +0800
                Re: jacobi_symbol.py Johann 'Myrkraverk' Oskarsson <johann@myrkraverk.invalid> - 2026-09-22 15:20 +0800
                Re: jacobi_symbol.py Johann 'Myrkraverk' Oskarsson <johann@myrkraverk.invalid> - 2026-09-25 23:32 +0800
          Re: ( n & -n ).bit_length() - 1 ## Really? "Johann \"Myrkraverk\" Oskarsson" <johann@myrkraverk.invalid> - 2026-09-20 04:52 +0800
  Re: ( n & -n ).bit_length() - 1 ## Really? Paul Rubin <no.email@nospam.invalid> - 2026-09-19 14:50 -0700

csiph-web